--- title: "Positive and Unlabeled Learning via Loss Decomposition and Centroid Estimation" authors: - "Hong Shi" - "Shaojun Pan" - "Jian Yang" - "Chen Gong" doi: "10.24963/ijcai.2018/373" url: "https://ijcai.org/proceedings/2018/373" pdf: "https://ijcai.org/proceedings/2018/0373.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "2689-2695" track: "Main track" keywords: - "Machine Learning: Classification" - "Machine Learning: Machine Learning" --- # Positive and Unlabeled Learning via Loss Decomposition and Centroid Estimation Hong Shi, Shaojun Pan, Jian Yang, Chen Gong *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 2689-2695. DOI: [10.24963/ijcai.2018/373](https://doi.org/10.24963/ijcai.2018/373) ## Abstract Positive and Unlabeled learning (PU learning) aims to train a binary classifier based on only positive and unlabeled examples, where the unlabeled examples could be either positive or negative. The state-of-the-art algorithms usually cast PU learning as a cost-sensitive learning problem and impose distinct weights to different training examples via a manual or automatic way. However, such weight adjustment or estimation can be inaccurate and thus often lead to unsatisfactory performance. Therefore, this paper regards all unlabeled examples as negative, which means that some of the original positive data are mistakenly labeled as negative. By doing so, we convert PU learning into the risk minimization problem in the presence of false negative label noise, and propose a novel PU learning algorithm termed ?Loss Decomposition and Centroid Estimation? (LDCE). By decomposing the hinge loss function into two parts, we show that only the second part is influenced by label noise, of which the adverse effect can be reduced by estimating the centroid of negative examples. We intensively validate our approach on synthetic dataset, UCI benchmark datasets and real-world datasets, and the experimental results firmly demonstrate the effectiveness of our approach when compared with other state-of-the-art PU learning methodologies. ## Full text ## 1 Introduction Traditional supervised machine learning methods usually assume that the negative training data are readily available, and a classifier can be established on both positive and negative training examples. However, in many cases the negative examples are missing, and manually labelling negative data is far more expensive than directly collecting the unlabeled data. To handle such situations, Positive and Unlabeled learning (PU learning) is proposed, of which the target is to accurately train a binary classifier by using positive data and unlabeled data. Here the unlabeled data might be positive or negative, however their groundtruth labels are unknown to the learning algorithm. Some preliminary researches on PU learning can be dated back to [Denis, 1998; De Comit´e et al., 1999; Nigam et al., 1998], which have shown that unlabeled data are helpful in building an accurate classifier. Recently, PU learning has attracted a great deal of attention due to its practical value and has been applied to solving various problems, such as information retrieval [Latulippe et al., 2013], outlier detection [Scott and Blanchard, 2009], text classification [Liu et al., 2003], and so on. According to how the unlabeled data are handled, existing PU learning methods can be attributed to three main categories. The first category follows the two-step strategy which firstly identifies the reliable negative data from unlabeled data, and then invokes an ordinary classifier to perform traditional supervised learning. [Liu et al., 2003; 2002; Li and Liu, 2003] are representative works belonging to this category. However, the identification of negative examples can be inaccurate, which may severely degrade the final model performance and lead to poor classification. Therefore, the methods belonging to the second category directly treat all unlabeled examples as negative and formulate PU learning as a cost-sensitive learning problem. By reweighting the training examples, the inaccurate data distribution carried by the observed training set can be calibrated to the potential correct one and thus the ideal data distribution can be approximated. For example, weighted Logistic regression [Lee and Liu, 2003] and weighted SVM [Elkan and Noto, 2008] adjust the data weights by imposing different regularization parameters on labeled and unlabeled examples. However, manually adjusting the regularization parameters could be rather empirical and is very likely to bring about unsatisfactory performance. To avoid tuning the parameters, several recent works focus on designing various unbiased risk estimators, which achieve the state-of-the-art performance. Specifically, [Du Plessis et al., 2014] develops a non-convex ramp loss to amend the data bias caused by the missing of negative examples. To overcome the defect brought by the non-convexity, a convex unbiased loss is presented in [Du Plessis et al., 2015], of which the key idea is to use a weighted ordinary convex loss function for unlabeled data and a weighted composite convex loss function for positive data. Similar to the second category, the last category also regards the unlabeled example as negative, however, with label noise [Yu et al., 2017a; 2017b; Cheng et al., 2017]. In other words, the potential positive examples in the unlabeled set are mislabeled as negative, and thus PU learning can be transformed into a noisy label learning problem. For example, biased SVM [Liu et al., 2003] deploys two trade-off parameters C+ and C- to weight positive errors and negative errors during training, respectively. Nevertheless, this method only utilizes free parameters to roughly control the noise rate and does not build specific model to deal with the label noise, so its performance is heavily dependent on the selection of C+ and C-. Considering that the third category that treats unlabeled set as noisy is more straightforward and more easily to implement than the first two categories, in this paper we formulate PU learning as a noisy label learning problem and propose a novel PU learning algorithm dubbed "Loss Decomposition and Centroid Estimation" (LDCE). To be specific, we take the labels of available positive training data as reliable and view the unlabeled examples as noisy negative data. Different from [Liu et al., 2003], in LDCE we explicitly model the label noise in negative set (i.e. the original unlabeled set) and convert PU learning into a risk minimization problem in the presence of negative label noise. First of all, we adopt different loss functions for positive examples and noisy negative examples. Secondly, we decompose the empirical loss on negative data into two parts, where only the second part is affected by the noisy data. Furthermore, according to [Gao et al., 2016], the risk minimization in the presence of label noise can be converted to the estimation of the centroid of the statistic labeled examples. Therefore, our problem is turned into the estimation of the centroid of noisy negative data. Thorough experiments on various synthetic and practical datasets demonstrate that the proposed approach is superior to the existing state-of-art methods on PU learning. ## 2 ProblemDescription Suppose that we have n training examples Sn = {(x1, y1),. . ., (xk, yk), (xk+1, yk+1),. . ., (xn, yn)} identically and independently drawn from some distribution D over X × Y, where xi denotes the input vector in feature space X and yi is the corresponding class label in output space Y = {+1,-1}. In Sn, the first k examples are positive (denoted as SP ), while the rest are unlabeled examples that might be positive or negative. Then the target of PU learning is to train a binary classifier h: X ×Y on Sn, such that h can assign accurate label sgn(h(x)) to the unseen test example x. As mentioned in Section 1, this paper treats all unlabeled examples as negative, in which the real positive examples are deemed as mislabeled. Therefore, we use ˜ SN = {(xk+1, ˜ yk+1), ..., (xn,˜ yn)} to denote the corrupted negative set in which the notation " ∼ " means that the corresponding labels yi =-1(i = k + 1,. . ., n) might be incorrect. Consequently, the entire training set for model training is formed by ˜ Sn =SP ∪ ˜ SN, and the clean version of ˜ SN is recorded by SN, in which all examples are correctly labeled. As a result, PU learning here is converted to the problem of learning under label noise. Note that in the studied case no noisy labels appear in the positive set SP while they only exist in ˜ SN. Besides, we use η to denote the prior of label noise rate in ˜ SN , which can be estimated via cross-validation [Natarajan et al., 2013] or other advanced methods [Liu and Tao, 2016]. Based Pr[ ˜ yi = -1|yi = 1] = η, Pr[˜ yi = 1|yi = -1] = 0, (1) where Pr[·] denotes probability. Given yi as the true label corresponding to the observed corrupted label ˜ yi, we have In (2), Pr[˜ yi = 1] is the prior of observed positive class that equals to k/n, then we can get the prior probability of true positive example as which is denoted by p for simplicity. Different from other works that estimate the class prior by cross-validation, the positive class prior Pr[yi = 1] in our work can be directly computed by (3). ## 3 Loss Decomposition Suppose h is an obtained classifier and the loss function is ℓ : Y × R → R, which penalizes the deviation from the predicted value h(x) and the groundtruth label y. In our case, the risk of classifier h (i.e. R(h, Sn)) on Sn is composed of two parts, where the first part is the loss on the clean positive examples and the second part is the loss on the corrupted negative examples, namely Note that the first termRP (h, SP ) in (4) can be easily computed as all the labels in SP are correct. However, the real value of second term RN(h, SN) is not accessible as the groundtruth labels of the examples in SN are unknown. Therefore, what follows is studying how to get the unbiased estimation of the second term. In this paper, we use hinge loss as the loss ℓ, so according to [Patrini et al., 2016], we can further decompose the hinge loss ℓ on the contaminated negative examples into two parts, which reaches where z is variable and the equation 2 holds due to an arithmetic trick of max(a, b) = (a + b)/2 + |b - a|/2. Since for any z, we have Eq. (5) can be further derived as In this formulation, the term in the first bracket is an even function that is not affected by noise, and the second term 12 (1 - z) is an odd function that is affected by noise. Consequently, only the second term in (7) reflects the impact of label noise which will be further studied in Section 4. According to (7), the upper bound of RN(h, SN) is formulated Therefore, the upper bound RN is employed to replace the original RN and it is simply denoted by RN in the subsequent explanations with a little abuse of notation. ## 4 Analysis of Noisy Negative Examples In this section, we analyze the classification risk on the corrupted negative examples ˜ SN. Section 3 has shown that RN(h, SN) can be divided into two parts, where the first part is label independent but the second part is influenced by the erroneous negative labels. Hence, we investigate the influence of noisy negative examples on the second term. Assume the linear classifier is hw(xi) = 〈w, xi〉, where w is the model parameter, then according to (8), we have Noise only exists in negative examples, hence the only thing we need to consider carefully is the corrupted negative examples. From the explanation of Eq. (7) in Section 3, we know that we only need to focus on the third term of Eq. (9) for dealing with label noise. Moreover, we also introduce the notion of negative example centroid that concerns the unlabeled examples in SN with true labels and true distribution D, namely µ(SN) = 1 n-k ∑ni=k+1 yixi and the corrupted negative set ˜ SN and corrupted distribution Dη, respectively. By substituting µ(SN) into RN(h, SN) and ignoring the constant term, (9) is transformed to Since we can only observe the corrupted ˜ SN supported by Dη rather than the true SN supported by D. The key for computing (10) lies in the estimation of µ(SN). To this end, we provide the following theorem: Theorem 1. Given η as the prior of label noise rate in ˜ SN and p as the prior probability of true positive example defined in (3), the means of true distribution D and the corrupted distribution Dη satisfy µ(Dη) = (1 - 2pη)µ(D). Similarly, the example centroid of the real SN and the corrupted negative set ˜ SN have the relationship E˜ y1,...,˜ yn [µ( ˜ SN)] = (1 - 2pη)µ(SN ). Proof. It is straightforward that and Theorem 1 informs us that µ(˜ SN)/(1 - 2pη) is an unbiased estimation of µ(SN). Besides, [Gao et al., 2016] shows that the random noise increases the covariance of yx, and may result in heavy-tailed distributions. Hence, we derive the covariance matrix Σ(µ(˜ SN)) of negative instance centroid µ( ˜ SN), which is given in the following theorem. Theorem 2. Given ˜ SN as the corrupted negative example, the empirical covariance matrix ˆΣ(µ(˜ SN)) is Besides, since We may easily get the covariance matrix by substituting (16) and (17) into (15). As a good approximation of (15), we can define the empirical covariance as (14) [Gao et al., 2016]. Algorithm 1 Median-of-means estimator of corrupted negative mean Input: The corrupted negative sample, ˜ SN; the number of groups g, g ≥ 1; Output: The median-of-means estimator, ˆµ(˜ SN ); - 2: Calculate the standard empirical mean µ(˜ SN [i] ) for each i ∈ [g] and each group ˜ SN [i] ; - 3: Calculate ri = median{µ(˜ SN [i] ) - µ( ˜ SN [j] )} for each i ∈ [g], and then set i∗ = argmini∈[g] ri; - 4: return ˆµ(˜ SN ). ## 5 The LDCE Algorithm Section 4 shows that we can estimate the true unlabeled example centroid µ(SN), which is significant to handle PU problem, by estimating the corrupted negative example centroid µ(˜ SN). In this paper, we adopt the recent generalized median-of-means estimator [Hsu and Sabato, 2014] to estimate µ(˜ SN). The basic idea is to randomly divide the corrupted negative set ˜ SN into g groups with almost equal size, and then return the generalized median of sample means for each group under ℓ2-norm metric. Algorithm 1 presents the detailed description about this process. Due to the influence of noise on the covariance of yx , that has been discussed in Section 4, here we impose a constraint on µ( ˜ SN), which is where ˆµ(˜ SN) is the output of Algorithm 1, ˆΣ(ˆµ(˜ SN )) is shown in Eq. (15), and β can be estimated by crossvalidation. Therefore, our PU learning model is formalized as s.t. (µ- ˆµ(˜ SN ))⊤ ˆΣ(ˆµ( ˜ SN ))(µ - ˆµ( ˜ SN )) ≤ β, where ℓ(yi〈w, xi〉) = max(0, 1 - yi〈w, xi〉), c = -(n - k)/2n, ϕ(yi, 〈w, xi〉) = [1-yi〈w, xi〉]++[1+yi〈w, xi〉]+, p = k/n(1 - η), and λ‖w‖2 is the regularization term to avoid overfitting. In this work, we use the Alternative Convex Search method to solve the optimization problem (19). Specially, after fixing µ, we can simply use the gradient descent algorithm to solve the minimization problem on w, which is Algorithm 2 Loss Decomposition and Centroid Estimation (LDCE) algorithm for PU learning Input: The corrupted sample ˜ Sn = {(x1, y1), . . . , (xk, yk), (xk+1, ˜ yk+1), . . . , (xn, ˜ yn)}, the noisy parameter η, the regularization parameter λ, the approximation β; Output: The optimal classifier parameter w; - 1: Call Algorithm 1 to give an estimation of ˆµ = ˆµ(˜ SN ); - 2: Calculate ˆΣ = ˆΣ(ˆµ(˜ SN)) by Eq. (14); - 3: Initialize t = 0 and w0; - 4: repeat - 5: Calculate µ=ˆµ+ˆΣ-1w√β/(w⊤ˆΣ-1w); - 6: Use gradient descent method to solve - 7: t = t +1; - 8: until convergence; - 9: return The converged w. For fixed w, after ignoring some constant terms, the optimization problem regarding µ is To deal with this constrained optimization problem, we can introduce a Lagrange variable ρ, and thus (22) By setting ∂L(µ,β) ∂µ = 0, we obtain By plugging Eq. (23) into Eq. (21), we have of which the solution is ρ = - c2 √w⊤( ˆΣ(ˆµ( ˜ SN )))-1w/β. By further plugging it into Eq. (23), we derive the solution of Eq. (23) as Algorithm 2 shows the detailed procedure of our algorithm. ## 6 Experiments In this section, we perform exhaustive experiments on one synthetic dataset, seven publicly available benchmark datasets and two real-world datasets. We compare our proposed method (dubbed as "LDCE") with state-of-the-art PU learning methods such as Weighted SVM (W-SVM) [Elkan and Noto, 2008], Unbiased PU (UPU) [Du Plessis et al., 2015] and Non-Negative PU (NNPU) [Kiryo et al., 2017]. Besides, LDCE is also compared with the traditional Linear SVM (L-SVM) for which the unlabeled examples are naively treated as negative. ## 6.1 Synthetic Dataset Firstly, we create a two-dimensional dataset consisted of two Gaussians as shown in Figure 1 (a). The dataset contains 500 positive examples and 500 negative examples, and each class corresponds to a Gaussian. We make 20% (η = 0.2) of the original positive examples and all negative examples to be unlabeled (see Figure 1 (b)), and examine whether different PU learning methods can accurately find the proper decision boundary for separating positive and negative examples. The results of various compared methods are shown in Figure 1 (c)∼(f), revealing that only our LDCE achieves 100% classification accuracy, which is higher than 99.8%, 99.7% and 94% obtained by W-SVM, UPU and L-SVM, respectively. Note that NNPU is not compared as this method does not output explicit decision function. Specifically, we see that many negative examples are classified as positive by the traditional L-SVM, so directly treating all unlabeled examples as negative is inappropriate for PU learning. Besides, although the performances of W-SVM and UPU are better than L-SVM, they fail to distinguish the ambiguous examples near the potentially correct decision boundary. Therefore, the superiority of LDCE to other existing models are demonstrated. ## 6.2 UCI Benchmark Dataset To demonstrate the effectiveness of our proposed method, we also conducted extensive experiments on seven datasets from UCI machine learning repository [Merz and Murphy, 1998]. The size of training set n and the feature dimensionality d for each dataset is presented in Table 1. All data features are normalized to [-1, 1] in advance. For each of the dataset illustrated in Table 1, we randomly pick 80% of the data for training and the rest 20% examples are used for testing. Then, we randomly select 20%, 30%, 40% ( i.e. η ∈ {0.2, 0.3, 0.4}) positive training examples and combine them with original negative set to compose the unlabeled set. Note that the division of positive set and unlabeled set under each η is kept identical for every compared method. In our experiment, we conduct 5-fold cross validation on all comparators and their mean test accuracies over the five trials are reported in Table 1. Furthermore, we also apply the t-test with significant level 0.1 to statistically examine whether our LDCE is significantly better than other methods. From the mean test accuracies reported in Table 1, we see that LDCE is consistently among the best two methods on the seven datasets. Apart from mushroom dataset, the performances of existing PU learning approaches can be significantly enhanced by LDCE as revealed by the t-test. Figure 1: The performances of various methods on synthetic dataset: (a) shows the real positive and unlabeled examples, (b) shows the positive and unlabeled examples for model training, (c)∼(f) display the decision boundaries generated by LDCE, UPU, W-SVM and LSVM, respectively. The incorrectly classified examples are highlighted by purple circles. ![Image](https://ijcai.org/proceedings/2018/fulltext/373/image_000000_440db57bdf1bf75d0294eb18bf5921cd3dfe2e5d95039bc965c86f481a3e7e5c.png) ## 6.3 Real-world Data We also conduct the experiments on two real-world datasets to evaluate the ability of our LDCE in dealing with practical problem. ## Handwritten Digit Recognition The USPS 1 dataset was adopted to assess the ability of various methods in recognizing the handwritten digits. This dataset contains 9298 digit images belonging to 10 classes, i.e. the digits "0"-"9". The resolution of all images is 16×16, so the pixel-wise feature we adopted was 256 dimensions, in which every dimension represents the gray value of corresponding pixel. We choose the digit images of "0" as positive, and regard the rest of digit images as negative examples. Therefore, there are 1553 positive examples and 7745 negative examples, and such class imbalance will pose a great challenge for the compared methodologies. The way for generating the positive set is the same as the manipulations in Section 6.2. Since this dataset is imbalanced, we apply two metrics, i.e. test accuracy and F-measure, to evaluate the performance of all methods. The results of various methods are presented in Table 2 and Figure 2, respectively. From the Table 2, we see that our proposed LDCE preforms better than other methods under different noise rates (η), in terms of test accuracy. From Figure 2, we observe that the F-measure obtained by LDCE is also higher than other methods on the two realworld datasets, which demonstrate the effectiveness of our proposed approach in dealing with imbalance data. 1 http://www.cad.zju.edu.cn/home/dengcai/Data/MLData.html Table 1: Comparison of mean test accuracies of various approaches on UCI datasets. √ (×) denotes that our approach is significantly better (worse) than the corresponding method revealed by the paired t-test with significance level 0.1. The best two results on each dataset are indicated in red and blue, respectively. | Dataset | (n, d) | Num of P | Num of N | η | W-SVM | UPU | NNPU | L-SVM | LDCE | |------------|-------------|------------|------------|-----|------------------|------------------|------------------|------------------|--------------| | | | | | 0.2 | 0.876 ± 0.04 √ | 0.888 ± 0.03 | 0.883 ± 0.03 √ | 0.775 ± 0.05 √ | 0.901 ± 0.03 | | vote | (435, 16) | 267 | 168 | 0.3 | 0.862 ± 0.05 | 0.885 ± 0.04 | 0.869 ± 0.02 | 0.834 ± 0.03 √ √ | 0.894 ± 0.04 | | | | | | 0.4 | 0.801 ± 0.09 | 0.802 ± 0.03 √ | 0.786 ± 0.03 √ | 0.747 ± 0.03 | 0.823 ± 0.05 | | | | | | 0.2 | 0.853 ± 0.03 √ | 0.854 ± 0.03 √ √ | 0.838 ± 0.03 √ | 0.822 ± 0.04 √ | 0.910 ± 0.02 | | balance | (625, 4) | 288 | 337 | 0.3 | 0.773 ± 0.12 | 0.805 ± 0.03 √ | 0.760 ± 0.11 | 0.773 ± 0.12 | 0.827 ± 0.03 | | | | | | 0.4 | 0.629 ± 0.05 √ | 0.685 ± 0.02 | 0.680 ± 0.04 √ | 0.626 ± 0.05 √ √ | 0.721 ± 0.03 | | | | | | 0.2 | 0.947 ± 0.01 √ | 0.952 ± 0.02 √ | 0.956 ± 0.01 √ | 0.933 ± 0.02 √ | 0.974 ± 0.02 | | breast | (683, 10) | 143 | 540 | 0.3 | 0.802 ± 0.02 √ √ | 0.795 ± 0.01 √ √ | 0.821 ± 0.03 | 0.798 ± 0.01 √ | 0.845 ± 0.03 | | | | | | 0.4 | 0.794 ± 0.01 | 0.791 ± 0.00 | 0.799 ± 0.02 √ | 0.789 ± 0.02 | 0.845 ± 0.04 | | | | | | 0.2 | 0.810 ± 0.04 √ √ | 0.811 ± 0.04 | 0.838 ± 0.02 | 0.796 ± 0.05 √ √ | 0.849 ± 0.03 | | australian | (690, 14) | 370 | 383 | 0.3 | 0.828 ± 0.01 | 0.842 ± 0.01 | 0.838 ± 0.03 √ √ | 0.825 ± 0.02 | 0.852 ± 0.02 | | | | | | 0.4 | 0.832 ± 0.04 | 0.801 ± 0.02 √ | 0.839 ± 0.03 | 0.809 ± 0.04 | 0.851 ± 0.02 | | | | | | 0.2 | 0.966 ± 0.01 √ √ | 0.958 ± 0.01 √ √ | 0.963 ± 0.01 √ | 0.864 ± 0.08 √ √ | 0.977 ± 0.01 | | benknote | (1372, 4) | 610 | 762 | 0.3 | 0.953 ± 0.02 √ | 0.952 ± 0.01 √ | 0.972 ± 0.01 | 0.775 ± 0.04 √ | 0.975 ± 0.02 | | | | | | 0.4 | 0.937 ± 0.01 | 0.929 ± 0.03 | 0.964 ± 0.01 | 0.808 ± 0.05 √ | 0.973 ± 0.01 | | | | | | 0.2 | 0.658 ± 0.09 √ √ | 0.764 ± 0.02 √ √ | 0.910 ± 0.04× | 0.526 ± 0.05 √ | 0.849 ± 0.03 | | mushroom | (8124, 112) | 3916 | 4208 | 0.3 | 0.688 ± 0.09 √ | 0.726 ± 0.01 | 0.864 ± 0.07× | 0.504 ± 0.01 √ | 0.750 ± 0.01 | | | | | | 0.4 | 0.510 ± 0.01 | 0.656 ± 0.04 | 0.750 ± 0.05× | 0.507 ± 0.01 | 0.658 ± 0.05 | | | | | | 0.2 | 0.794 ± 0.03 √ √ | 0.785 ± 0.04 √ | 0.830 ± 0.02 | 0.630 ± 0.02 √ √ | 0.840 ± 0.02 | | web | (11055, 31) | 6157 | 4898 | 0.3 | 0.691 ± 0.06 √ | 0.729 ± 0.05 √ √ | 0.822 ± 0.02 | 0.652 ± 0.08 √ | 0.827 ± 0.02 | | | | | | 0.4 | 0.625 ± 0.03 | 0.732 ± 0.07 | 0.817 ± 0.01 | 0.612 ± 0.01 | 0.821 ± 0.01 | ## Violent Behavior Detection Recently, intelligent monitoring technique for detecting violent behavior has gained incresing of attention due to its great practical significance. In this section, we utilize the HockeyFight 2 dataset and apply our proposed approach and other PU methods to fight behavior detection. The HockeyFight dataset is made up of 1000 video clips collected in ice hockey competitions, of which 500 contain fight behavior and 500 are non-fight sequences. We classify the clips with fighting and without fighting by using various PU learning methods including L-SVM, W-SVM, UPU, NNPU and our LDCE. Similar to [Gong et al., 2015], after adopting the space-time interest point (STIP) and motion SIFT (MoSIFT) as action descriptors, each video clip of the dataset can be represented as a histogram over 100 visual words by further using the Bag-of-Words (BoW) quantization. Hence, every clip in the dataset was characterized by a 100-dimensional feature vector. Similar to Section 6.2, the proportions of training examples and test examples are also maintained as 80% and 20%, respectively, and the noise rate η also ranges from 0.2 to 0.4. The test accuracies and F-measure values achieved by the compared methods are presented in Table 2 and Figure 2, respectively, which clearly indicate that our LDCE achieves the top-level performance among all the comparators. Particularly, it can be noted that the F-measure of LDCE is as high as 0.783 when the noise rate is 0.4. In contrast, the second best L-SVM only achieves the F-measure of 0.671. Therefore, our LDCE is still able to render very impressive results even though a large number of positive examples are "hidden" in the original unlabeled set. 2 http://visilab.etsii.uclm.es/personas/oscar/FightDetection/index.html Table 2: Comparison of test accuracies of various approaches on two real-world datasets including HockeyFight and USPS. The best result on each dataset is indicated in bold. | Dataset | (n, d) | η | W-SVM | UPU | NNPU | L-SVM | LDCE | |-------------|-------------|-----|---------|-------|--------|---------|--------| | HockeyFight | (1000, 100) | 0.2 | 0.841 | 0.845 | 0.845 | 0.825 | 0.860 | | HockeyFight | | 0.3 | 0.780 | 0.765 | 0.745 | 0.745 | 0.791 | | HockeyFight | | 0.4 | 0.681 | 0.742 | 0.735 | 0.514 | 0.752 | | USPS | (9298, 256) | 0.2 | 0.925 | 0.929 | 0.916 | 0.896 | 0.934 | | USPS | | 0.3 | 0.743 | 0.901 | 0.893 | 0.733 | 0.911 | | USPS | | 0.4 | 0.812 | 0.892 | 0.866 | 0.768 | 0.901 | Figure 2: The F-measure of various PU learning methods on (a) HockeyFight and (b) USPS. The highest F-measure value under each noise rate η is marked by red. ![Image](https://ijcai.org/proceedings/2018/fulltext/373/image_000001_53bbc52e37031e4d1d7daac97ee471bbbaa91f9d4fb352b90921a0b72ca48498.png) ## 7 Conclusion This paper proposes a novel PU learning algorithm dubbed "Loss Decomposition and Centroid Estimation" (LDCE). By treating the unlabeled examples as negative with false negative label error, we convert PU learning to the noisy label learning problem, and use the loss decomposition technique to explicitly model the noisy labels. Based on loss decomposition, we shed light on that the unbiased estimation of labeled example centroid helps to reduce the adverse effect of noise. Thorough experimental results on both synthetic and practical datasets show that the proposed method is more effective than the state-of-the-art PU learning methods. In the future, it is worthwhile to extend our LDCE model to non-linear case by introducing the kernel trick. ## Acknowledgments This research is supported by NSF of China (No: 61602246, U1713208 and 61472187), 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: DZXX-027), the 973 Program No.2014CB349303, and Program for Changjiang Scholars. ## References 1. [Cheng et al., 2017] Jiacheng Cheng, Tongliang Liu, Kota- giri Ramamohanarao, and Dacheng Tao. Learning with bounded instance-and label-dependent label noise. arXiv preprint arXiv:1709.03768, 2017. 2. [De Comité et al., 1999] Francesco De Comité, Franc ¸ois Denis, Rémi Gilleron, and Fabien Letouzey. Positive and unlabeled examples help learning. In International Con- ference on Algorithmic Learning Theory, pages 219-230, 1999. 3. [Denis, 1998] Franc ¸ois Denis. PAC learning from positive statistical queries. In International Conference on Algo- rithmic Learning Theory, pages 112-126, 1998. 4. [Du Plessis et al., 2014] Marthinus C Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In Advances in Neural Information Processing Systems, pages 703-711, 2014. 5. [Du Plessis et al., 2015] Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In International Confer- ence on Machine Learning, pages 1386-1394, 2015. 6. [Elkan and Noto, 2008] Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled da- ta. In Proceedings of The 14th ACM SIGKDD Internation- al Conference on Knowledge Discovery and Data Mining, pages 213-220, 2008. 7. [Gao et al., 2016] Wei Gao, Lu Wang, Yu-Feng Li, and Zhi- Hua Zhou. Risk minimization in the presence of label noise. In AAAI Conference on Artificial Intelligence, pages 1575-1581, 2016. 8. [Gong et al., 2015] Chen Gong, Tongliang Liu, Dacheng Tao, Keren Fu, Enmei Tu, and Jie Yang. Deformed graph laplacian for semisupervised learning. IEEE Transaction- s on Neural Networks and Learning Systems, 26:2261- 2274, 2015. 9. [Hsu and Sabato, 2014] Daniel Hsu and Sivan Sabato. Heavy-tailed regression with a generalized median-of- means. In International Conference on Machine Learning, pages 37-45, 2014. 10. [Kiryo et al., 2017] Ryuichi Kiryo, Gang Niu, Marthinus C du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. In Advances in Neural Information Processing Systems, pages 1674- 1684, 2017. 11. [Latulippe et al., 2013] Maxime Latulippe, Alexandre Drouin, Philippe Giguere, and Franc ¸ois Laviolette. Accelerated robust point cloud registration in natural environments through positive and unlabeled learning. In International Joint Conference on Artificial Intelligence, pages 2480-2487, 2013. 12. [Lee and Liu, 2003] Wee Sun Lee and Bing Liu. Learning with positive and unlabeled examples using weighted lo- gistic regression. In International Conference on Machine Learning, volume 3, pages 448-455, 2003. 13. [Li and Liu, 2003] Xiaoli Li and Bing Liu. Learning to clas- sify texts using positive and unlabeled data. In Internation- al Joint Conference on Artificial Intelligence, volume 3, pages 587-592, 2003. 14. [Liu and Tao, 2016] Tongliang Liu and Dacheng Tao. Clas- sification with noisy labels by importance reweighting. IEEE Transactions on pattern analysis and machine in- telligence, pages 447-461, 2016. 15. [Liu et al., 2002] Bing Liu, Wee Sun Lee, Philip S Yu, and Xiaoli Li. Partially supervised classification of text docu- ments. In International Conference on Machine Learning, pages 387-394, 2002. 16. [Liu et al., 2003] Bing Liu, Yang Dai, Xiaoli Li, Wee Sun Lee, and Philip S Yu. Building text classifiers using pos- itive and unlabeled examples. In The IEEE International Conference on Data Mining, volume 2, pages 179-186, 2003. 17. [Merz and Murphy, 1998] Christopher J Merz and Patrick M Murphy. UCI Repository of machine learning databases. 1998. 18. [Natarajan et al., 2013] Nagarajan Natarajan, Inderjit S D- hillon, Pradeep K Ravikumar, and Ambuj Tewari. Learn- ing with noisy labels. In Advances in Neural Information Processing Systems, pages 1196-1204, 2013. 19. [Nigam et al., 1998] Kamal Nigam, Andrew McCallum, Se- bastian Thrun, Tom Mitchell, et al. Learning to classify text from labeled and unlabeled documents. In AAAI Con- ference on Artificial Intelligence, volume 792, 1998. 20. [Patrini et al., 2016] Giorgio Patrini, Frank Nielsen, Richard Nock, and Marcello Carioni. Loss factorization, weakly supervised learning and label noise robustness. In Interna- tional Conference on Machine Learning, pages 708-717, 2016. 21. [Scott and Blanchard, 2009] Clayton Scott and Gilles Blan- chard. Novelty detection: Unlabeled data definitely help. In Artificial Intelligence and Statistics, pages 464-471, 2009. 22. [Yu et al., 2017a] Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. arXiv preprint arXiv:1711.09535, 2017. 23. [Yu et al., 2017b] Xiyu Yu, Tongliang Liu, Mingming Gong, Kun Zhang, and Dacheng Tao. Transfer learning with label noise. arXiv preprint arXiv:1707.09724, 2017.