{'fraction_non_alphanumeric': 0.03570065950836649, 'fraction_numerical': 0.013626205919223852, 'mean_word_length': 4.424242424242424, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Negative Training Data Can be Harmful to Text Classification

This paper studies the effects of training data on binary text classification and postulates that negative training data is not needed and may even be harmful for the task. Traditional binary classification involves building a classifier using labeled positive and negative training examples. The classifier is then applied to classify test instances into positive and negative classes. A fundamental assumption is that the training and test data are identically distributed. However, this assumption may not hold in practice. In this paper, we study a particular problem where the positive data is identically distributed but the negative data may or may not be so. Many practical text classification and retrieval applications fit this model. We argue that in this setting negative training data should not be used, and that PU learning can be employed to solve the problem. Empirical evaluation has been conducted to support our claim. This result is important as it may fundamentally change the current binary classification paradigm.


Introduction
Text classification is a well-studied problem in machine learning, natural language processing, and information retrieval. To build a text classifier, a set of training documents is first labeled with predefined classes. Then, a supervised machine learning algorithm (e.g., Support Vector Machines (SVM), naïve Bayesian classifier (NB)) is applied to the training examples to build a classifier that is subsequently employed to assign class labels to the instances in the test set. In this paper, we focus on binary text classification with two classes (i.e. positive and negative classes).
Most learning methods assume that the training and test data have identical distributions. However, this assumption may not hold in practice, i.e., the training and the test distributions can be different. The problem is called covariate shift or sample selection bias (Heckman 1979;Shimodaira 2000;Zadrozny 2004;Huang et al. 2007;Sugiyama et al. 2008;Bickel et al. 2009). In general, this problem is not solvable because the two distributions can be arbitrarily far apart from each other. Various assumptions were made to solve special cases of the problem. One main assumption was that the conditional distribution of the class given an instance is the same over the training and test sets (Shimodaira 2000; Huang et al. 2007;Bickel et al. 2009).
In this paper, we study another special case of the problem in which the positive training and test samples have identical distributions, but the negative training and test samples may have different distributions. We believe this scenario is more applicable for binary text classification. As the focus in many applications is on identifying positive instances correctly, it is important that the positive training and the positive test data have the same distribution. The distributions of the negative training and negative test data can be different. We believe that this special case of the sample selection bias problem is also more applicable for machine learning. We will show that a partially supervised learning model, called PU learning (learning from Positive and Unlabeled examples) fits this special case quite well (Liu et al. 2002).
Following the notations in (Bickel et al. 2009), our special case of the sample selection bias problem can be formulated as follows: We are given a training sample matrix X L with row vectors x 1 , …, x k . The positive and negative training instances are governed by different unknown distributions p (x|λ) and p(x|δ) respectively. The element y i of vector y = (y 1 , y 2 , …, y k ) is the class label for training instance x i (y i ∈{+1, -1}, where +1 and -1 denote positive and negative classes respectively) and is drawn based on an unknown target concept p(y|x). In addition, we are also given an unlabeled test set in matrix X T with rows x k+1 , …, x k+m . The (hidden) positive test instances in X T are also governed by the unknown distribution p(x|λ), but the (hidden) negative test instances in X T are governed by an unknown distribution, p(x|θ), where θ may or may not be the same as δ. p(x|θ) and p(x|δ) can differ arbitrarily, but there is only one unknown target conditional class distribution p(y|x).
This problem setting is common in many applications, especially in those applications where the user is interested in identifying a particular type of documents (i.e. binary text classification). For example, we want to find sentiment analysis papers in the literature. For training a text classifier, we may label the papers in some EMNLP proceedings as sentiment analysis (positive) and non-sentiment analysis (negative) papers. A classifier can then be built to find sentiment analysis papers from ACL and other EMNLP proceedings. However, this labeled training set will not be appropriate for identifying sentiment analysis papers from the WWW, KDD and SIGIR conference proceedings. This is because although the sentiment analysis papers in these proceedings are similar to those in the training data, the non-sentiment analysis papers in these conferences can be quite different. Another example is email spam detection. A spam classification system built using the training data of spam and non-spam emails from a university may not perform well in a company. The reason is that although the spam emails (e.g., unsolicited commercial ads) are similar in both environments, the non-spam emails in them can be quite different.
One can consider labeling the negative data in each environment individually so that only the negative instances relevant to the testing environment are used to train the classifier. However, it is often impractical (if not impossible) to do so. For example, given a large blog hosting site, we want to classify its blogs into those that discuss stock markets (positive), and those that do not (negative). In this case, the negative data covers an arbitrary range of topics. It is clearly impractical to label all the negative data.
Most existing methods for addressing the sam-ple selection bias problem work as follows. First, they estimate the bias of the training data based on the given test data using statistical methods. Then, a classifier is trained on a weighted version of the original training set based on the estimated bias. In this paper, we show that our special case of the sample selection bias problem can be solved in a much simpler and somewhat radical manner-by simply discarding the negative training data altogether. We can use the positive training data and the unlabeled test data to build the classifier using the PU learning model (Liu et al. 2002). PU learning was originally proposed to solve the learning problem where no labeled negative training data exist. Several algorithms have been developed in the past few years that can learn from a set of labeled positive examples augmented with a set of unlabeled examples. That is, given a set P of positive examples of a particular class (called the positive class) and a set U of unlabeled examples (which contains both hidden positive and hidden negative examples), a classifier is built using P and U to classify the data in U as well as future test data into two classes, i.e., those belonging to P (positive) and those not belonging to P (negative). In this paper, we also propose a new PU learning method which gives more consistently accurate results than the current methods.
Our experimental evaluation shows that when the distributions of the negative training and test samples are different, PU learning is much more accurate than traditional supervised learning from the positive and negative training samples. This means that the negative training data actually harms classification in this case. In addition, when the distributions of the negative training and test samples are identical, PU learning is shown to perform equally well as supervised learning, which means that the negative training data is not needed. This paper thus makes three contributions. First, it formulates a new special case of the sample selection bias problem, and proposes to solve the problem using PU learning by discarding the negative training data. Second, it proposes a new PU learning method which is more accurate than the existing methods. Third, it experimentally demonstrates the effectiveness of the proposed method and shows that negative training data is not needed and can even be harmful. This result is important as it may fundamentally change the way that many practical classification problems should be solved.

Related Work
A key assumption made by most machine learning algorithms is that the training and test samples must be drawn from the same distribution. As mentioned, this assumption can be violated in practice. Some researchers have addressed this problem under covariate shift or sample selection bias. Sample selection bias was first introduced in the econometrics by Heckman (1979). It came into the field of machine learning through the work of Zadrozny (2004). The main approach in machine learning is to first estimate the distribution bias of the training data based on the test data, and then learn using weighted training examples to compensate for the bias (Bickel et al. 2009). Shimodaira (2000) and Sugiyama and Muller (2005) proposed to estimate the training and test data distributions using kernel density estimation. The estimated density ratio could then be used to generate weighted training examples. Dudik et al. (2005) and Bickel and Scheffer (2007) used maximum entropy density estimation, while Huang et al. (2007) proposed kernel mean matching. Sugiyama et al. (2008) and Tsuboi et al. (2008) estimated the weights for the training instances by minimizing the Kullback-Leibler divergence between the test and the weighted training distributions. Bickel et al. (2009) proposed an integrated model. In this paper, we adopt an entirely different approach by dropping the negative training data altogether in learning. Without the negative training data, we use PU learning to solve the problem (Liu et al. 2002;Yu et al. 2002;Denis et al. 2002;Lee and Liu, 2003;Liu et al. 2003;Denis et al. 2003;Li et al. 2007;Elkan and Noto, 2008;Li et al. 2009;Li et al. 2010). We will discuss this learning model further in Section 3.
Another related work to ours is transfer learning or domain adaptation. Unlike our problem setting, transfer learning addresses the scenario where one has little or no training data for the target domain, but has ample training data in a related domain where the data could be in a different feature space and follow a different distribution. A survey of transfer learning can be found in (Pan and Yang 2009). Several NLP researchers have studied transfer learning for different applications (Wu et al. 2009a;Yang et al. 2009;Agirre & Lacalle 2009;Wu et al. 2009b;Sagae & Tsujii 2008;Goldwasser & Roth 2008;Li and Zong 2008;Andrew et al. 2008;Chan and Ng 2007;Jiang and Zhai 2007;Zhou et al. 2006), but none of them addresses the problem studied here.

PU Learning Techniques
In traditional supervised learning, ideally, there is a large number of labeled positive and negative examples for learning. In practice, the negative examples can often be limited or unavailable. This has motivated the development of the model of learning from positive and unlabeled examples, or PU learning, where P denotes a set of positive examples, and U a set of unlabeled examples (which contains both hidden positive and hidden negative instances). The PU learning problem is to build a classifier using P and U in the absence of negative examples to classify the data in U or a future test data T. In our setting, the test set T will also act as the unlabeled set U.
PU learning has been investigated by several researchers in the past decade. A study of PAC learning for the setting under the statistical query model was given in (Denis, 1998). Liu et al. reported the sample complexity result and showed how the problem may be solved (Liu et al., 2002). Subsequently, a number of practical algorithms (e.g., Liu et al., 2002;Yu et al., 2002; were proposed. They generally follow a two-step strategy: (i) identifying a set of reliable negative documents RN from the unlabeled set; and then (ii) building a classifier using P (positive set), RN (reliable negative set) and U-RN (unlabelled set) by applying an existing learning algorithm (such as naive Bayesian classifier or SVM) iteratively. There are also some other approaches based on unbalanced errors (e.g., Liu et al. 2003;Lee and Liu, 2003;Elkan and Noto, 2008).
In this section, we first introduce a representative PU learning technique S-EM, and then present a new technique called CR-SVM.

S-EM Algorithm
S-EM (Liu et al. 2002) is based on naïve Bayesian classification (NB) (Lewis, 1995;Nigam et al., 2000) and the EM algorithm (Dempster et al. 1977). It has two steps. The first step uses a spy technique to identify some reliable negatives (RN) from the unlabeled set U and the second step uses the EM algorithm to learn a Bayesian classifier from P, RN and U-RN.
Step 1: Extracting reliable negatives RN from U using a spy technique The spy technique in S-EM works as follows (Figure 1): First, a small set of positive examples (denoted by SP) called "spies" is randomly sampled from P (line 2). The default sampling ratio in S-EM is s = 15%. Then, an NB classifier is built using P-SP as the positive set and U∪SP as the negative set (lines [3][4][5]. The NB classifier is applied to classify each u ∈ U∪SP, i.e., to assign a probabilistic class label p(+|u) (+ means positive) to u. The idea of the spy technique is as follows. Since the spy examples were from P and were put into U as negatives in building the NB classifier, they should behave similarly to the hidden positive instances in U. We thus can use them to find the reliable negative set RN from U. Using the probabilistic labels of spies in SP and an input parameter l (noise level), a probability threshold t is determined. Due to space constraints, we are unable to explain l. Details can be found in (Liu et al. 2002). t is then used to find RN from U (lines 8-10).
RN ← RN ∪ {u}; Step 2: Learning using the EM algorithm Given the positive set P, the reliable negative set RN, and the remaining unlabeled set U-RN, we run EM using NB as the base learning algorithm. The naive Bayesian (NB) method is an effective text classification algorithm. There are two different NB models, namely, the multinomial NB and the multi-variate Bernoulli NB. In this paper, we use the multinomial NB since it has been observed to perform consistently better than the multivariate Bernoulli NB (Nigam et al., 2000).
Given a set of training documents D, each document d i ∈ D is an ordered list of words. We use w d i ,k to denote the word in position k of d i , where each word is from the vocabulary V = {w 1 , … , w |v| }, which is the set of all words considered in classifi-cation. We also have a set of classes C = {c 1 , c 2 } representing positive and negative classes. For classification, we compute the posterior probability Pr(c j |d i ). Based on the Bayes rule and multinomial model, we have (1) and with Laplacian smoothing, (2) where N(w t ,d i ) is the number of times that the word w t occurs in document d i , and Pr(c j |d i ) {0,1} depending on the class label of the document. Assuming that probabilities of words are independent given the class, we have the NB classifier: EM (Dempster et al. 1977) is a popular class of iterative algorithms for maximum likelihood estimation in problems with incomplete data. It is often used to address missing values in the data by computing expected values using the existing values. The EM algorithm consists of two steps, the E-step and the M-step. The E-step fills in the missing data, and M-step re-estimated the parameters. This process is iterated till satisfaction (i.e. convergence). For NB, the steps used by EM are identical to those used to build the classifier (equations (3) for the E-step, and equations (1) and (2) for the Each document in P is assigned the class label 1; 2. Each document in RN is assigned the class label −1; 3. Learn an initial NB classifier f from P and RN, using Equations (1) and (2); 4. Repeat

5.
For each document d i in U-RN do // E-Step 6.
Using the current classifier f compute Pr(c j |d i ) using Equation (3); 7.
Learn a new NB classifier f from P, RN and U-RN by computing Pr(c j ) and Pr(w t |c j ), using Equations (1) and (2); // M-Step 8. Until the classifier parameters stabilize 9. The last iteration of EM gives the final classifier f ; 10. For each document d i in U do 11.
Output d i as a positive document; 13.
else Output d i as a negative document In EM, Pr(c j |d i ) takes the value in [0, 1] instead of {0, 1} in all the three equations.
The algorithm for the second step of S-EM is given in Figure 2. Lines 1-3 build a NB classifier f using P and RN. Lines 4-8 run EM until convergence. Finally, the converged classifier is used to classify the unlabeled set U (lines 10-13).

Proposed CR-SVM
As we will see in the experiment section, the performance of S-EM can be weak in some cases. This is due to the mixture model assumption of its NB classifier (Nigam et al. 2000), which requires that the mixture components and classes be of oneto-one correspondence. Intuitively, this means that each class should come from a distinctive distribution rather than a mixture of multiple distributions. In our setting, however, the negative class often has documents of mixed topics, e.g., representing the broad class of everything else except the topic(s) represented by the positive class.
There are some existing PU learning methods based on SVM which can deal with this problem, e.g., Roc-SVM . Like S-EM, Roc-SVM also has two steps. The first step uses Rocchio classification (Rocchio, 1971) to find a set of reliable negatives RN from U. In particular, this method treats the entire unlabeled set U as negative documents and then uses the positive set P and the unlabeled set U as the training data to build a Rocchio classifier. The classifier is subsequently applied to classify the unlabeled set U. Those documents that are classified as negative are then considered as reliable negative examples RN. The second step of Roc-SVM runs SVM iteratively (instead of EM). Unlike NB, SVM does not make any distributional assumption.
However, Roc-SVM does not do well due to the weakness of its first step in finding a good set of reliable negatives RN. This motivates us to propose a new SVM based method CR-SVM to detect a better quality RN set. The second step of CR-SVM is similar to that in Roc-SVM.
Step 1: Extracting reliable negatives RN from U using Cosine and Rocchio The first step of the proposed CR-SVM algorithm for finding a RN set consists of two sub-steps: Sub-step 1 (extracting the potential negative set PN using the cosine similarity): Given the positive set P and the unlabeled set U, we extract a set of potential negatives PN from U by computing the similarities of the unlabeled documents in U and the positive documents in P. The idea is that those documents in U that are very dissimilar to the documents in P are likely to be negative.
1. PN = ∅; 2. Represent each document in P and U as vectors using the TF-IDF representation; 3. For each d j ∈ P do 4.

;
6. For each d j ∈ P do 7. compute cos(pr, d j ) using Equation (4); 8. Sort all the documents d j ∈P according to cos (pr, d j ) in decreasing order; 9. ω = cos(pr, d p ) where d p is ranked in the position of (1-l)*|P|; 10. For each d i ∈ U do 11.

Figure 3. Extracting potential negatives PN from U
The detailed algorithm is given in Figure 3. Each document in P and U is first represented as a vector d = (q 1 , q 2 , …, q n ) using the TF-IDF scheme (Salton 1986). Each element q i (i=1, 2, …, n) in d represents a word feature w i . A positive representative vector (pr) is built by summing up the documents in P and normalizing it (lines 3-5). Lines 6-7 compute the similarities of each document d j in P with pr using the cosine similarity, cos(pr, d j ).
Line 8 sorts the documents in P according to their cos(pr, d j ) values. We want to filter away as many as possible hidden positive documents from U so that we can obtain a very pure negative set. Since the hidden positives in U should have the same behaviors as the positives in P in terms of their similarities to pr, we set their minimum similarity as the threshold value ω which is the minimum similarity before a document is considered as a potential negative document: In a noiseless scenario, using the minimum similarity is acceptable. However, most real-life applications contain outliers and noisy artifacts. Using the absolute minimum similarity may be unreliable; the similarity cos(pr, d j ) of an outlier docu- ment d j in P could be near 0 or smaller than most (or even all) negative documents. It would therefore be prudent to ignore a small percentage l of the documents in P most dissimilar to the representative positive (pr) and assume them as noise or outliers. Since we do not know the noise level of the data, to be safe, we use a noise level l = 5% as the default. The final classification result is not sensitive to l as long as it is not too big. In line 9, we use the noise level l to decide on a suitable ω. Then, for each document d i in U, if its cosine similarity cos(pr, d i ) < ω, we regard it as a potential negative and store it in PN (lines 10-12).
Our experiment results showed that PN is still not sufficient or big enough for accurate PU learning. Thus, we need to do a bit more work to find the final RN. Sub-step 2 (extracting the final reliable negative set RN from U using Rocchio with PN): At this point, we have a positive set P and a potential negative set PN where PN is a purer negative set than U. To extract the final reliable negatives, we employ the Rocchio classification to build a classifier RC using P and PN (We do not use SVM here as it is very sensitive to the noise in PN). Those documents in U that are classified as negatives by RC will then be regarded as reliable negatives, and stored in set RN.
The algorithm for this sub-step is given in Figure 4. Following the Rocchio formula, a positive and a negative prototype vectors p and n are built (lines 3 and 4), which are used to classify the documents in U (lines 5-7). α and β are parameters for adjusting the relative impact of the positive and negative examples. In this work, we use α = 16 and β = 4 as recommended in (Buckley et al. 1994).

Step 2: Learning by running SVM iteratively
This step is similar to that in Roc-SVM, building the final classifier by running SVM iteratively with the sets P, RN and the remaining unlabeled set Q (Q = U -RN).
The algorithm is given in Figure 5. We run SVM classifiers S i (line 3) iteratively to extract more and more negative documents from Q. The iteration stops when no more negative documents can be extracted from Q (line 5). There is, however, a danger in running SVM iteratively, as SVM is quite sensitive to noise. It is possible that during some iteration, SVM is misled by noisy data to extract many positive documents from Q and put them in the negative set RN. If this happens, the final SVM classifier will be inferior. As such, we employ a test to decide whether to keep the first SVM classifier or the final one. To do so, we use the final SVM classifier obtained at convergence (called S last , line 9) to classify the positive set P to see if many positive documents in P are classified as negatives. Roc-SVM chooses 5% as the threshold, so CR-SVM also uses this threshold. If there are 5% of positive documents (5%*|P|) in P that are classified as negative, it indicates that SVM has gone wrong and we should use the first SVM classifier (S 1 ). In our experience, the first classifier is always quite strong; good results can therefore be achieved even without catching the last (possibly better) classifier.
The main difference between Roc-SVM and CR-SVM is that Roc-SVM does not produce PN. It simply treats the unlabeled set U as negatives for extracting RN. Since PN is clearly a purer negative set than U, the use of PN by CR-SVM helps extract a better quality reliable negative set RN which subsequently allows the final classifier of CR-SVM to give better results than Roc-SVM.
Note that the methods (S-EM and CR-SVM) are all two-step algorithms in which the first step and the second step are independent of each other. The algorithm for the second step basically needs a good set of reliable negatives RN extracted from U. This means that one can pick any algorithm for the first step to work with any algorithm for the second step. For example, we can also have CR-EM which uses the algorithm (shown in Figures 3 and 4) of the first step of CR-SVM to combine with the algorithm of the second step of S-EM. CR-EM actually works quite well as it is also able to exploit the more accurate reliable negative set RN extracted using cosine and Rocchio.

Empirical Evaluation
We now present the experimental results to support our claim that negative training data is not needed and can even harm text classification. We also show the effectiveness of the proposed PU learning methods CR-SVM and CR-EM. The following methods are compared: (1) traditional supervised learning methods SVM and NB which use both positive and negative training data; (2) PU learning methods, including two existing methods S-EM and Roc-SVM and two new methods CR-SVM and CR-EM, and (3) one-class SVM (Schölkop et al., 1999) where only positive training data is used in learning (the unlabeled set is not used at all).
We used LIBSVM 1 for SVM and one-class SVM, and two publicly available 2 PU learning techniques S-EM and Roc-SVM. Note that we do not compare with some other PU learning methods such as those in and Elkan and Noto, 2008 as the purpose of this paper is not to find the best PU learning method but to show that PU learning can address our special sample selection bias problem. Our current methods already do very well for this purpose.

Datasets and Experimental Settings
We used two well-known benchmark data collections for text classification, the Reuters-21578 collection 3 and the 20 Newsgroup collection 4 . Reuters-21578 contains 21578 documents. We used the most populous 10 out of the 135 categories following the common practice of other researchers. 20 Newsgroup has 11997 documents from 20 discussion groups. The 20 groups were also categorized into 4 main categories.
We have performed two sets of experiments, and just used bag-of-words as features since our objective in this paper is not feature engineering.
(1) Test set has other topic documents. This set of experiments simulates the scenario in which the negative training and test samples have different distributions. We select positive, negative and other topic documents for Reuters and 20 Newsgroup, and produce various data sets. Using these data sets, we want to show that PU learning can do bet-1 http://www.csie.ntu.edu.tw/~cjlin/libsvm/ 2 http://www.cs.uic.edu/~liub/LPU/LPU-download.html 3 http://www.research.att.com/~lewis/reuters21578.html 4 http://people.csail.mit.edu/jrennie/20Newsgroups/ ter than traditional learning that uses both positive and negative training data.
For the Reuters collection, each of the 10 categories is used as a positive class. We randomly select one or two of the remaining categories as the negative class (denoted by Neg 1 or Neg 2), and then we randomly choose some documents from the rest of the categories as other topic documents. These other topic documents are regarded as negatives and added to the test set but not to the negative training data. They thus introduce a different distribution to the negative test data. We generated 20 data sets (10*2) for our experiments this way.
The 20 Newsgroup collection has 4 main categories with sub-categories 5 ; the sub-categories in the same main category are relatively similar to each other. We are able to simulate two scenarios: (1) the other topic documents are similar to the negative class documents (similar case), and (2) the other topic documents are quite different from the negative class documents (different case). This allows us to investigate whether the classification results will be affected when the other topic documents are somewhat similar or vastly different from the negative training set. To create the training and test data for our experiments, we randomly select one sub-category from a main category (cat 1) as the positive class, and one (or two) subcategory from another category (cat 2) as the negative class (again denoted by Neg 1 or Neg 2). For the other topics, we randomly choose some docu-ments from the remaining sub-categories of cat 2 for the similar case, and some documents from a randomly chosen different category (cat 3) (as the other topic documents) for the different case. We generated 8 data sets (4*2) for the similar case, and 8 data sets (4*2) for the different case.
The training and test sets are then constructed as follows: we partition the positive (and similarly for the negative) class documents into two standard subsets: 70% for training and 30% for testing. In order to create different experimental settings, we vary the number of the other topic documents that are added to the test set as negatives, controlled by a parameter α, which is a percentage of |TN|, where |TN| is the size of the negative test set without the other topic documents. That is, the number of other topic documents added is α × |TN|.
(2) Test set has no other topic documents. This set of experiments is the traditional classification in which the training and test data have the same distribution. We employ the same data sets as in (1) but without having any other topic documents in the test set. Here we want to show that PU learning can do equally well without using the negative training data even in the traditional setting.

Results with Other Topic Documents in Test Set
We show the results for experiment set (1), i.e. the distributions of the negative training and test data are different (caused by the inclusion of other topic documents in the test set, or the addition of other topic documents to complement existing negatives in the test set). The evaluation metric is the F-score on the positive class (Bollmann and Cherniavsky, 1981), which is commonly used for evaluating text classification. Figure 6 shows the comparison results when the negative class contains only one category of documents (Neg 1), while Figure 7 shows the results when the negative class contains documents from two categories (Neg 2) in the Reuters collection. The data points in the figures are the averages of the results from the corresponding datasets. Our proposed method CR-SVM is shown to perform consistently better than the other techniques. When the size of the other topic documents (xaxis) in the test set increases, the F-scores of the two traditional learning methods SVM and NB decreased much more dramatically as compared with the PU learning techniques. The traditional learning models were clearly unable to handle different distributions for training and test data. Among the PU learning techniques, the proposed CR-SVM gave the best results consistently. Roc-SVM did not do consistently well as it did not manage to find high quality reliable negatives RN sometimes. The EM based methods (CR-EM and S-EM) performed well in the case when we had only one negative class ( Figure 6). However, it did not do well in the situation where there were two negative classes (Figure 7) due to the underlying mixture model assumption of the naïve Bayesian classifier. One-class SVM (OSVM) performed poorly because it did not exploit the useful information in the unlabeled set at all.

Results on 20 Newsgroup data
Recall that for the 20 Newsgroup data, we have two settings: similar case and different case. The comparison results are given in Figure 8 (Neg 1) and Figure 9 (Neg 2). We observe that CR-EM, S-EM and CR-SVM all performed well. EM based methods (CR-EM and S-EM) have a slight edge over CR-SVM. Again, the F-scores of the traditional supervised learning (SVM and NB) deteriorated when more other topic documents were added to the test set, while CR-EM, S-EM and CR-SVM were able to remain unaffected and maintained roughly constant F-scores. When the negative class contained documents from two categories (Neg 2), the F-scores of the traditional learning dropped even more rapidly. Both Roc-SVM and One-class SVM (OSVM) performed poorly, due to the same reasons given previously.  The results are shown in Figures 10 (Neg 1) and 11 (Neg 2). The trends are similar to those for the similar case, except that the performance of the traditional supervised learning methods (SVM and NB) dropped even more rapidly with more other topic documents. As the other topic documents have very different distributions from the negatives in the training set in this case, they really confused the traditional classifiers. In contrast, the three PU learning techniques were still able to perform consistently well, regardless of the number of other topic documents added to the test data.  In summary, the results showed that learning with negative training data based on the traditional paradigm actually harms classification when the identical distribution assumption does not hold.

Results without Other Topic Documents in Test Set
Given an application, one may not know whether the identical distribution assumption holds. The above results showed that PU learning is better when it does not hold. How about when the assumption does hold? To find out, we compared the results of SVM, NB, and three PU learning methods using the datasets without any other topic documents added to the test set. In this case, the training and test data distributions are the same. Table 1 shows the results for this scenario. Note that for PU learning, the negative training data were not used. The traditional supervised learning techniques (SVM and NB), which made full use of the positive and negative training data, only performed just about 1-2% better than the PU learning method CR-SVM (which is not statistically significant based on paired t-test). This suggests that we can do away with negative training data, since PU learning can perform equally well without them. This has practical importance since the full coverage of negative training data is hard to find and to label in many applications.
From the results in Figures 6-11 and Table 1, we can conclude that PU learning can be used for binary text classification without the negative training data (which can be harmful for the task). CR-SVM is our recommended PU learning method based on its generally consistent performance.

Conclusions
This paper studied a special case of the sample selection bias problem in which the positive training and test distributions are the same, but the negative training and test distributions may be different. We showed that in this case, the negative training data should not be used in learning, and PU learning can be applied to this setting. A new PU learning algorithm (called CR-SVM) was also proposed to overcome the weaknesses of the current two-step algorithms.
Our experiments showed that the traditional classification methods suffered greatly when the distributions are different for the negative training and test data, but PU learning does not. We also showed that PU learning performed equally well in the ideal case where the training and test data have identical distributions. As such, it can be advantageous to discard the potentially harmful negative training data and use PU learning for classification.
In our future work, we plan to do more comprehensive experiments to compare the classic supervised learning and PU learning techniques with different kinds of settings, for example, by varying the ratio between positive and negative examples, as well as their sizes. It is also important to explore how to catch the best iteration of the SVM/NB classifier in the iterative running process of the algorithms. Finally, we would like to point out that it is conceivable that negative training data could still be useful in many cases. An interesting direction to explore is to somehow combine the extracted reliable negative data from the unlabeled set and the existing negative training data to further enhance learning algorithms.