Positive unlabeled learning via wrapper-based adaptive sampling

1 Introduction

Traditional supervised learning algorithms require labels of both positive and negative instances for building a binary classification model. In various applications, however, obtaining negative data could be difficult especially in domains that lack precise knowledge and definition of negative instances [Calvo et al., 2007]. For example, defining genes that are unrelated to a disease is difficult as there can be genes that are unknown to be related to the disease and therefore contaminating the negative sample set. In such cases, positive unlabeled learning techniques are proposed to model from labeled positive instances augmented with unlabeled instances comprising both unknown positive and negative instances [Denis et al., 2005; Li et al., 2009].

Current techniques proposed for positive unlabeled learning can roughly be categorised into (1) heuristic, (2) biasbased, (3) one-class, and (4) bootstrap sampling approaches. Heuristic approaches often partition the learning process into two steps where negative instances are firstly identified by using heuristic methods such as information retrieval techniques [Li and Liu, 2003], Bayesian methods [Liu et al., 2003], Expectation Maximization algorithms [Nigam et al., 1998;

Liu et al., 2002], or domain knowledge [Yang et al., 2012], and a final classification model is created using labeled positive instances and unlabeled negative instances identified in the first step. One key disadvantage of most heuristic approaches is the requirement of a pre-defined threshold to determine either to include or exclude a potential negative instance obtained from unlabeled data for model training. Finding the optimal threshold for negative instance selection could be data dependent and often influence greatly on the accuracy of the final model. The lack of formality for many heuristic methods also limited their generality.

Bias-based approaches, on the other hand, treat all unlabeled data as negative instances and employ a traditional learning procedure, except a "bias" is introduced to weight the classification model and/or the cost function towards positive class in that predictions made from unlabeled data are penalised less for been positive to account for unknown positive instances been labeled as negatives [Elkan and Noto, 2008]. This approach was utilised for learning biased SVM [Liu et al., 2003], logistic model [Lee and Liu, 2003] and Bayes classifier [Nigam et al., 2000]. Elkan and Noto [Elkan and Noto, 2008] have subsequently formulated the bias-based approach in a general framework that could be used with a large selection of classification models. However, bias-based approaches often rely on training data for estimating the "bias" to be applied for model correction. Hence, part of the training data need to be utilised for bias estimation or a crossvalidation procedure is conducted. This is unattractive especially when the training data are limited because the estimation of the "bias" coefficient could deviate significantly, causing under- or over-correction and thus poor classification model.

Alternatively, positive unlabeled learning can also be formulated as a one-class learning problem where only positive labels are used for training a classification model [Li et al., 2011]. This has give rise to a set of methods that adhere to the same principle of one-class learning but tailored for positive unlabeled learning [Denis et al., 2002; Calvo et al., 2007]. Given the similarity between one-class learning and positive unlabeled learning, many more oneclass learning algorithms can also be easily tuned for positive unlabeled learning [Khan and Madden, 2014]. The drawback of adjusting one-class learning methods for positive unlabeled learning however is that they generally rely on generative classification models and ignore unlabeled data. Therefore, more labeled positive instances may be required to achieve comparable performance to methods that effectively utilise both labeled and unlabeled instances.

Recently, methods based on bootstrap sampling have been proposed to create ensemble of models for positive unlabeled learning [Mordelet and Vert, 2014; Claesen et al., 2015; Yang et al., 2016]. In such settings, unlabeled instances are treated as negatives and bootstrap sampling are performed on unlabeled instances and subsequently concatenated with labeled positive instances to train base classifiers that form an ensemble. The key idea is to take advantage of instability of predictions, caused potentially by the random inclusion of unlabeled positive instances, and aggregate a final stable prediction. These bootstrap sampling approaches adhere to and exploit the advantages of bagging-like procedure [Breiman, 1996]. Nevertheless, since all unlabeled instances are treated as negative data, the random subsets sampled from unlabeled data still contains incorrect labels. The base classifiers, therefore, still suffer from unwanted label noise which propagates and affects the performance of the final ensemble model.

This study extends on bootstrap sampling approaches by introducing a novel wrapper-based adaptive sampling (AdaSampling) procedure. Similar to previously proposed methods [Mordelet and Vert, 2014; Claesen et al., 2015], initially all unlabeled instances are treated as negative examples and are equally likely to be selected for model training. Then AdaSampling differs from bootstrap sampling approaches in that the procedure "wraps" around a classification model and prediction uncertainties of unlabeled instances from the model are incorporated for each subsequent iterations of sampling to reduce the probability of selecting potential unknown positive instances as negative examples for model training (Figure 1). AdaSampling is generic and can be applied with any learning model that outputs classification probabilities. It does not require additional training data for bias estimation nor a heuristic procedure for selecting negative instances. This allows both labeled and unlabeled data to be utilised for model training without introducing any prediction bias in the learning model. Furthermore, AdaSampling approach can be easily extended for ensemble learning where different negative instances are drawn and combined with labeled positive to create diverse base classifiers. This enables ensemble model with AdaSampling to make effective usage of unlabeled data while also prevent potential noise propagation from applying bootstrap sampling directly to all unlabeled data.

Our empirical studies suggest that AdaSampling requires very few iterations to accurately distinguish unlabeled positive and negative instances even with very high positive to negative instance ratio in unlabeled data. We next compared AdaSampling based single and ensemble models with the state-of-the-art bias-based approach and bootstrap sampling approach using Support Vector Machine (SVM) and kNearest Neighbours (kNN) and a panel of evaluation metrics on several real-world datasets with different ratios of unlabeled positive instances. Our experimental results demonstrate that AdaSampling significantly improve on classification for both SVM and kNN, and their performance compared favourably to state-of-the-art methods. Together, this study offers a conceptually simple, flexible, yet powerful approach for positive unlabeled learning.

2 Methods

2.1 AdaSampling

It is helpful to view the positive unlabeled learning problem as discriminating positive and negative instances from a dataset with negative examples been contaminated by hidden positive instances. In this formulation, the problem of positive unlabeled learning is reduced to a traditional classification problem where all unlabeled instances are treated as negative instances. Let us denote the labeled instances as L (i.e. y = 1), unlabeled instances as U and assume that there are m labeled and n unlabeled instances. In positive unlabeled learning where the label information is not available for U, a traditional classifier can be trained by labeling all U as negatives (i.e. y=0), sampling with equal probability from all instances in U and combining them with L:

where S0 ⊂ U and the superscript 0 of S0 and D0 is the iteration index (cf., Alg. 1). A classification model can be fitted using this training dataset (Eq. 1):

The above classification model (Eq. 2) is the starting point of AdaSampling where an instance s ∈ U will be selected to be a negative example for subsequent training with a probability of 1 - p(y = 1|s). The training data can be updated after a set of instances Si ⊂ U are selected (with replacement):

where i indexes iteration of sampling. By utilising the prediction probabilities of the fitted model on instances fromU, AdaSampling can update the training dataset [Di , y] (Eq. 3) to reduce the chance of selecting unlabeled positive instances as negative training examples. This will lead to updated prediction probabilities pi (y|x1), ..., pi (y|xm+n) of all instances including the n instances of U from which AdaSampling can be repeatedly utilised to update the training dataset.

2.2 AdaSampling for Classification

Single model. AdaSampling can be used with various classification algorithms for positive unlabeled learning. Akin to wrapper based feature selection [Kohavi and John, 1997], here the procedure wraps around a classification model to iteratively prioritise negative instances from unlabeled data. This procedure therefore tunes the data with respect to a given predictive model. Criteria such as the following:

can be utilised for termination of the iterative sampling and the predicted probabilities from the final iteration can be used for classification of instances from both the labeled and unlabeled data. Here j = 1, ...,m+n is the index of all instances in the data. We set ε to be 0.01, requiring smaller than 1% change in mean prediction probabilities of all instances for the process to terminate.

Algorithm 1 summarises this procedure in pseudocode.

Algorithm 1: AdaSampling for single model

Data: Positive unlabeled data L and U Result: Predicted label of all instances y 1 p0 ← 1; // initialise probability vector for all instances 2 S0 ← sampling(U, p0U); // select negative instances with probability p0 fromU 3 [D0 , y] ← [L, y = 1] ∪ [S0 , y = 0]; // label initial training data 4 i ← 0; 5 do 6 i ← i + 1; 7 // train a model and classify all instances 8 pi (y|x1), ..., pi (y|xm+n) ← predict(hθ(x; [Di-1 , y]), L ∪ U); 9 // adaptive sampling from x ∈ U w.r.t updated probabilities 10 Si ← sampling(U, piU); 11 [Di , y] ← [L, y = 1] ∪ [Si , y = 0]; 12 while Eq. 4 > ε; 13 y ←classify(hθ(x; [Di , y]),L∪U);

Ensemble of models. Alternatively, we can apply weighted sampling from U using piU, from the last AdaSampling interaction, as weights to create different negative subsets S∗k (k = 1, ...K). This allows for creating base models bk (k = 1, ...K) each trained on a different training set [L, y = 1] ∪ [S∗k , y = 0] for ensemble prediction. The key advantage of this procedure for ensemble learning is that prediction uncertainties of U are exploited multiple times to make effective usage of instances in U, avoiding potential high variance introduced by training a single model for classification. Algorithm 2 summarises AdaSampling based ensemble learning procedure in pseudocode.

3 Experimental Procedure

This section summarises the datasets used for evaluation and describe the performance evaluation strategy.

3.1 Synthetic Datasets

Synthetic datasets were used to analyse the behaviour of AdaSampling. In particular, we simulated 100 labeled pos-

Data: Positive unlabeled data L and U Result: Predicted label of all instances y 1 p0 ← 1; 2 S0 ← sampling(U, p0U); 3 [D0 , y] ← [L, y = 1] ∪ [S0 , y = 0]; 4 i ← 0; 5 do 6 i ← i + 1; 7 pi (y|x1), ..., pi (y|xm+n) ← predict(hθ(x; [Di-1 , y]), L ∪ U); 8 Si ← sampling(U, piU); 9 [Di , y] ← [L, y = 1] ∪ [Si , y = 0]; 10 while Eq. 4 > ε; 11 // create an ensemble of models 12 hEθ ←Null; 13 for k ∈ 1...K do 14 S∗k ← sampling(U, piU); 15 [Dk , y] ← [L, y = 1] ∪ [S∗k , y = 0]; 16 hEθ ← hEθ ⋃ hbk θ (x; [Dk , y]); 17 end

18 y ←classify(hEθ ;L∪U);

itive instances (denoted as L+) from a normal distribution N(6, 1) and 300 unlabeled negative instances (denoted as U-) from a normal distribution N(4, 1). Then, 50 or 100 unlabeled positive instances (denoted as U+) were added into the data to simulate "easy" and "hard" scenarios, respectively. Together, this gives two synthetic datasets where in the "easy" scenario there are 100 labeled positive instances and 350 unlabeled instances (a ratio of 1:0.5:3 for L+, U+ and U-), and in the "hard" scenario there are 100 labeled positive instances and 400 unlabeled instances (a ratio of 1:1:3 for L+, U+ and U-).

3.2 Real-World Datasets and Cross-Validation

We utilised five benchmark datasets for performance evaluation. These include breast cancer diagnosis (Breast), prediction free electrons in the ionosphere data (Ionosphere), sonar prediction of mines vs. rocks (Sonar), the Wisconsin database of breast cancer (WDBC), and the Pima Indians diabetes dataset (Pima). All these datasets were obtained from UC Irvine Machine Learning Repository [Lichman, 2013]

To simulate positive unlabeled learning scenarios, we treated instances from the negative class as unlabeled and introduced 50% and 67% of unlabeled positive instances with respect to the positive class by randomly removing label information of 1/2 or 2/3 of instances from the positive class, creating an "easy" and a "hard" scenarios. This gives 2 configurations of each dataset on which the evaluation experiments were performed (Table 1).

We used a multi-layered repetitive 5-fold cross-validation (CV) procedure to evaluate the performance of each method. Specifically, label information of instances from the positive class were randomly removed. This is repeated 5 times each with a different set of selected instances and comprise the first layer of randomisation. Subsequently, the data is split for 5fold CV and this is repeated 10 times each with a different split point. This gives the second layer of randomisation each is nested with the first layer of 5-fold CV. The performance of each method is the average of each trail plus and minus the mean standard error with respect to a given evaluation matric described below.

3.3 Classification Algorithms and Evaluation Metrics

We applied AdaSampling with support vector machine (SVM) and k-nearest neighbour (kNN) classification algorithms. SVM and kNN are typical examples of eager and lazy learning algorithms, respectively, and therefore represent two different methods that could be used together with AdaSampling. An SVMwith radial basis function kernel (C=1) and a kNN with k=3 were used across all positive unlabeled methods as well as the baseline to provide objective comparison between each positive unlabeled learning methods.

The evaluation matrices utilised for performance comparison are sensitivity (Se), specificity (Sp), F1 score, and geometric mean (GM). Area under the curve (AUC) is not included as a comparison metric because it is not effective for evaluating bias-based approach where the ranking of the predictions often remain the same [Elkan and Noto, 2008], leading to the same ROC curve but adjusted thresholds. Given that all benchmark datasets used in this study have roughly balanced class distribution, the F1 score and geometric mean provide a good trade-off between sensitivity and specificity for method comparison. Specifically, each of the matric is defined as following:

where TP, TN, FP, and FN are true positives, true negatives, false positives, and false negatives.

4 Results

This section presents the experimental results from using synthetic datasets and performance comparison using real-world datasets. All the data and code are available from the project repository 1 .

4.1 Analysis on Synthetic Datasets

We first evaluated on whether AdaSampling would allow classification algorithms to recover unlabeled positive instances from synthetic datasets. As can be seem from Figure 2, initially, unlabeled positive instances generally receive low classification probabilities with respect to (w.r.t) positive class. However, after only 2 iterations, classifiers coupled with AdaSampling procedure are able to drastically increase classification probabilities with respect to the positive class for most unlabeled positive instances. These results indicate that AdaSampling is highly effective in adaptive learning and converges in very few iterations.

Figure 3 shows decision boundaries created by each classification algorithms. Baseline results correspond to classification by treating all unlabeled instances simply as negative class examples. Results from AdaSampling correspond to applying Alg. 1 to create final classification models. It is apparent that decision boundaries created by all classification models in baseline settings significantly over-penalise positive instances (brown straps of Figure 3). Expectedly, such over-penalisation increase with the number of unlabeled positive instances (compare results under brown strap in Figure 3 (a) and (b)). AdaSampling facilitates classification models to recover a large proportion of labeled as well as unlabeled positive instances from been over-penalised by reducing the chance of selecting unlabeled positive instances and therefore extending decision boundaries around positive instances (green straps of Figure 3).

1 https://github.com/PengyiYang/AdaSampling

0 2 4 6 8 10 0 2 4 6 8 10

Figure 3: Comparison of baseline (i.e. treat all unlabeled instances as negative examples) and AdaSampling assisted classification on synthetic data. Decision boundaries of SVM and kNN on (a) "easy" and (b) "hard" dataset.

4.2 Classification of Real-World Datasets

Table 2 and 3 compare SVM and kNN classification on five read-world datasets using baseline approach (i.e. treating all unlabeled instances as negative examples), biasbased approach ("BiasModel") described in [Elkan and Noto, 2008], bagging-like approach ("BagModel") described in [Mordelet and Vert, 2014], and AdaSampling-based single model ("AdaSingle") and ensemble of models ("AdaEnsemble") proposed here. The classification of SVM and kNN on the original dataset (i.e. both positive and negative instances are defined) are performed to provide gold standards.

Direct application of both SVM and kNN to positive unlabeled data gives low predictive sensitivities (Baseline, Table 2 and 3) and the sensitivity decreases with the increase of unlabeled positive instances ("hard" cases). BiasModel improves predictive sensitivities in most cases but suffered from low specificities in Pima dataset classification. It appears that BiasModel over-corrected towards positive class in Pima dataset. This demonstrates a potential problem for relying on correcting the initial classifier trained by treating all unlabeled instances as negatives. If too many unlabeled positive instances are used as negative examples, the classification models will have poor quality, resulting in invalid correction.

BagModel appears to improve moderately on predictive sensitivities but the overall performance is lower them other alternative positive unlabeled learning approaches according to F1 score and geometric mean. This is expected as in BagModel no explicit mechanism is applied to deal with unlabeled positive instances. While the bootstrap sampling on unlabeled instances may avoid selecting unlabeled positive instances, this is not enforced as the sampling is completely random. In comparison, AdaSampling-based approaches achieved the highest prediction accuracy in terms of F1 score and geometric mean in all tested datasets and in both "easy" and "hard" cases regardless the classification algorithms (i.e SVM and kNN). Moreover, AdaEnsemble outperformed AdaSingle in most cases, suggesting an added advantage of incorporating heterogenous models using AdaSampling. It is worth noting that in a few cases, the performance of AdaSampling-based approach even outperformed the gold standard where all original labels were used for learning. This suggest that AdaSampling not only can recover missing label information but also could identify and correct potential label noise in the original datasets.

5 Conclusion

In this study, we proposed an adaptive sampling approach, called AdaSampling, for positive unlabeled learning. The proposed approach inheres the spirit of wrapper classification in which a classification model is used iteratively to assess the likelihood of each instance with respect to each class category. AdaSampling is a flexible framework and can be utilised to optimise data for individual classification model as well as constructing more complex ensemble models. Our experimental results demonstrated that both the single classification model and the ensemble of models derived from AdaSampling perform significantly better than those without using AdaSampling and in most cases also outperform other stat-of-the-art approaches for positive unlabeled learning.

We note that with minor modifications, AdaSampling can be easily extended for (1) multi-class classification and (2) class label noise identification and correction. The current study forms the basis of our future work on these directions.

Acknowledgements

This work is supported by Australian Research Council(ARC)/Discovery Early Career Researcher Award (DE170100759) to Pengyi Yang and National Health and Medical Research Council (NHMRC)/Career Development Fellowship (1105271) to Jean Yang.