Positive and Unlabeled Learning with Label Disambiguation

1 Introduction

Collecting a large amount of labeled data, especially labeled negative data, is a critical bottleneck in many real-world machine learning applications due to the laborious manual annotation or the difficulty of collecting negative data. In contrast, positive and unlabeled data can often be collected easily. This has led to the development of Positive and Unlabeled (PU) learning [Denis et al., 2005], which aims at learning a binary classifier only from positive and unlabeled data without the assistance of negative data. Recently, PU learning has gained lots of popularity in tackling many realworld scenarios such as software clone detection [Wei and Li, 2018], protein function prediction [Youngs et al., 2014;

Given its broad applicability as mentioned above, PU learning has attracted a great deal of research attention in recent years. Effective algorithms have been developed which can be roughly divided into three categories. The first category [Liu et al., 2002; Li and Liu, 2003] firstly identifies some reliable negative examples from the unlabeled set, and then employs the reliable negative as well as the original positive examples to train a traditional supervised classifier. The second category [Lee and Liu, 2003; Shi et al., 2018] takes PU leaning problem as a one-side label noise learning problem, which directly treats the unlabeled examples as negative ones. Particularly, the undiscovered positive examples in the unlabeled set are regarded as mislabeled, while no negative examples are mislabeled as positive. The last category [Elkan and Noto, 2008; Youngs et al., 2015; Du Plessis et al., 2014; Du Plessis et al., 2015] imposes different weights on the loss values incurred by simultaneously treating unlabeled examples as positive and negative, and thus transferring PU learning into a cost-sensitive learning problem. However, the ground-truth label of each unlabeled example is definite and unique, so simultaneously evaluating every unlabeled example as positive and negative under the framework of empirical risk minimization will inevitably introduce the label noise, leading to the imperfect performance.

To address this drawback, this paper proposes a novel PU leaning algorithm dubbed "Positive and Unlabeled learning with Label Disambiguation" (PULD). To be specific, we first treat PU learning problem as a Partial Label Learning (PLL) [Jin and Ghahramani, 2003] problem, where we regard the unlabeled examples as ambiguously labeled as positive and negative, and then employ the disambiguation technique, which is widely used in PLL, to robustly determine the real label of every unlabeled example. PLL aims to learn from ambiguous labeling information where each training example is associated with a set of candidate labels, among which only one label is valid [Cour et al., 2011; Gong et al., 2018; Feng and An, 2018; Chen et al., 2018]. Recent successful PLL methods have devised various disambiguation regularizers to identify the single ground-truth label from the candidate label set associated with each training example [Nguyen and Caruana, 2008; Wu and Zhang, 2018], which play an important role in boosting the PLL performance.

In our PU learning case, we take each unlabeled example as a partially labeled example with the candidate label set {1, 2}, and then utilize the margin based disambiguation strategy to enlarge the margin between the most likely label and the less likely one. As a result, the ground-truth label in the candidate label set can be effectively highlighted. Besides, a manifold regularizer with geometric knowledge of the original data is applied [Zhou et al., 2004; Belkin et al., 2006; Gong et al., 2019b], so that the similar examples in the feature space are assigned similar labels. Furthermore, we theoretically derive the generalization error bound of the proposed PULD by analyzing its Rademacher complexity, and intensive experiments on both benchmark and real-world datasets clearly demonstrate the superiority of the proposed method to the state-of-the-art PU learning approaches.

2 Our Method

In this section, we first establish our proposed PULD model, and then explain its iterative optimization process.

2.1 Model

Assume that there are n training examples S = {(x1, y1), . . . , (xp, yp), (xp+1, yp+1), . . . , (xn, yn); n = p + u} identically and independently drawn from some distribution D over X × Y, where X ∈ Rd and Y = {1, 2} denote the feature space and label space, respectively. For the convenience of the subsequent derivations, we follow the setting of multi-class classification, where negative examples are labeled as 1 and positive examples are labeled as 2. In S, the first p elements with the label {yi}pi=1 = 2 constitute the positive set P, and the rest u elements form the unlabeled set U in which the label of each example can be either 1 or 2 but not known.

In the training stage, our target is to find a real-valued scoring function h : X ×Y → R based on the training set S = P∪U, and the classification is performed according to the score, i.e. argmaxy∈Y h(x, y). Firstly, we build a KNN graph G = 〈V, E〉 over the training set S where V is the vertex set consisted of all xi ∈ S, and E is the edge set describing the similarity between these nodes. Further, A is the adjacency matrix of G, and its (i, j)-th element Aij encodes the similarity between xi and xj, which is computed by Aij =exp(-‖xi-xj‖2 /(2δ2 )) with δ being the Gaussian kernel width if xi and xj are linked, and Aij = 0 otherwise. Therefore, the normalized adjacency matrix adopted by us is ¯A = D-1/2AD-1/2 with D being the diagonal degree matrix of which the (i, i)-th element is Dii = ∑j Aij . Moreover, we define the mapping Φ(x, y) :X×Y ↦→F which projects the example-label pair (x, y) to Φ(x, y)∈F, namely

with d being the dimensionality of the input feature x, and 1(a) being an indicator function which returns 1 if a is true and 0 otherwise. Let y = (y1, . . . , yp, yp+1, . . . , yn) be the ground-truth labels of training examples. Then given the classifier as h(x, y) = ω⊤Φ(x, y), and ξ = {ξi}pi=1 and

η = {ηi}p+u i=p+1 as slack variables, our model is formulated as

where α, β, and γ are nonnegative trade-off parameters, and c is the proportion of positive examples in unlabeled set U.

In (2), the first term is used to present overfitting. The second term along with the constraint (3) imposed on P requires that for every xi∈P, the score ω⊤Φ(xi, 2) with the correct label yi=2 should be larger than the score ω⊤Φ(xi, 1) associated with the incorrect label yi=1, by at least 1-ξi. The third term as well as the constraint (4) enlarges the margin between the most likely label and the less likely one for each unlabeled example xi ∈U, in which the score associated with the most likely label y′ (i.e. maxy′ ω⊤Φ(xi, y′i )) should be larger than the score associated with the less likely one y′′ (i.e. maxy′′ i ̸=y′i ω⊤Φ(xi, y′′ i )), by at least 1-ηi. The last term ensures that the similar examples in the feature space should obtain similar labels. Constraint (5) requires the number of positive examples in U to be identical to uc, where the estimation of c is deferrd to Section 4.1.

Since we regard the unlabeled examples in U as ambiguously labeled as positive and negative, and the candidate label set of unlabeled examples can be denoted as {1, 2}, so we follow multi-class SVM [Crammer and Singer, 2001] and partial label learning [Yu and Zhang, 2017] to equip our model with good label discriminability. Therefore, the unique groundtruth label of every unlabeled example can be precisely highlighted. After we have learned the model parameter ω, a test example xi is classified as yi = argmaxyi∈Y ω⊤Φ(xi, yi).

Note that once the ground-truth labels {yi}p+u i=p+1 of the unlabeled examples in U are determined, our algorithm proceeds to maximize the canonical multi-class margin over each xi ∈ P ∪ U, i.e. ω⊤Φ(xi, yi) - maxy′i ̸=yi ω⊤Φ(xi, y′i ). Therefore, by introducing the slack variables ν = {νi}ni=1 , the previous model can be transformed to

In above model, the constraint (7) enforces the maximum margin between different label responses for each training example. In addition, the constraint (8) enforces that the ground-truth label yi should take a value in the candidate label set {1, 2}.

Note that our model is different from the LapSVM [Belkin et al., 2006] for semi-supervised learning, as LapSVM does not contain the label disambiguation regularizer as our PULD. Furthermore, if LapSVM is employed for PU learning, it will incorrectly classify all unlabeled examples to positive due to the absence of negative training data.

2.2 Optimization

Since our model (6)-(9) involves mixed-type variables (i.e. integer variables y, and continuous variables ω and ν), so its optimization is non-trivial. In this section, an alternating optimization procedure is devised to find the optimal solution.

Note that the variable y appears in both the second term and the third term of (6), so it is difficult to be updated all at once. Therefore, we adopt the variable splitting technique and introduce an auxiliary variable z = {z1, . . . , zn}. As a result, our model (6)-(9) is transformed to

where the last term in (10) is to keep y and z to be consistent, and λ is a trade-off parameter. Now, we are going to solve the three subproblems associated with ω, y, and z, respectively. Update ω. By fixing y and z, the subproblem related to ω is

Note that (11) coincides with the well-studied multi-class maximum margin formulation [Crammer and Singer, 2001]. Therefore, (11) can be readily solved by utilizing any off-theshelf implementation for multi-class SVM [Fan et al., 2008]. Update y. By dropping the unrelated terms to y in (10), the subproblem regarding y is

Let ζ yi i = ω⊤Φ(xi, yi)-maxy′i ̸=yi ω⊤Φ(xi, y′i ), then according to the first two constraints of (12), we have νi = max(0, 1 - ζ yi i ), so the first term of the objective function in (12) can be written as

Let Y = [Yij]n×2 be the binary-valued presentation of y, where Yij =1 indicates that the label of example xi is j, and 0 otherwise. Similarly, we may define Z=[Zij ]n×2. By further defining the i-th row of an n×2 coefficient matrix C as:

where M is a user-specfied large number to keep the label of each positive example to be constant, we know that the formulation (13) can be transformed to

Since Y and Z are both binary-valued, the second term of the objective function in (12) can be written as

By Combining (12), (13), (15), and (16), the subproblem related to Y (i.e. the binary-valued representation of y) can be finally transformed to

where the first constraint ∑2j=1 Yij = 1 ensures that each training example has a unique ground-truth label and the second constraint ∑ni=1 Yij = uc + p controls the amount of classified positive examples.

Note that (17) is a binary integer programming (BIP) problem. By relaxing Yij ∈ {0, 1} as Yij ∈ [0, 1], it can be efficiently solved by employing standard Linear Programming (LP) solvers such as the simplex algorithm or the interior point algorithm [Boyd and Vandenberghe, 2004], where y can be computed based on yi = arg maxj Yij . Update z. The subproblem regarding z is

Considering that the last term in (18) is usually difficult to optimize, here we replace the indicator function with a surrogate ℓ2 norm term, therefore (18) can be converted to

According to [Zhou et al., 2004], the closed form solution of (19) can be expressed as

Algorithm 1 The algorithm for solving PULD

Input: positive set P, unlabeled set U; trade-off parameters µ, γ, and λ; stopping criteria ϵ, iter max;

• 1: Initialize ω = 0, z = y = 0;
• 2: Construct K-NN graph and compute ¯A;
• 3: Initialize the coefficient matrix C, where {Ci·}pi=1 = (0, 1) and {Ci·}u+p i=p+1 = (1/2, 1/2);
• 4: Initialize the ground-truth label y via solving (17);
• 5: while not converge do
• 6: Objold = Obj;
• 7: Update ω via solving (11);
• 8: Update C via (14);
• 9: Update y via solving (17);
• 10: Update z via solving (19);
• 11: Compute the objective function value Obj via (10);
• 12: iter := iter + 1;
• 13: Check the convergence conditions: Obj - Objold < ϵ or iter > iter max;

14: end while

Output: optimized classifier parameter ω.

Therefore, we can get z according to zi = arg maxj Zij .

The entire optimization procedure of our PULD is summarized in Algorithm 1, in which the alternating procedure is guaranteed to converge according to [Hong and Luo, 2017].

3 Theoretical Analysis

In this section, we study the generalizability of the proposed PULD algorithm. In our PU learning case, the hypothesis is defined on a scoring function h ∈ H : X × Y → R with H denoting the hypothesis space. The label associated with the input x is the one resulting in the largest score h(x, y) when y ∈ Y, which defines the mapping

where h(x, y) = ω⊤Φ(x, y). We may define the margin loss on positive examples ρp(x, y) and unlabeled examples ρu(x, y) asρp(x, y) = h(x, y) - maxy′ ̸=yh(x, y′ ) (22)

To get the empirical margin loss for our PU learning case, we first introduce the following margin loss function [Gong et al., 2019a]:

where ρ is the margin. Let ρ(p) > 0 and ρ(u) > 0 denote the margins for positive and unlabeled examples, respectively, then we may define the empirical margin loss as

Let ˆh be any learned classifier output by PULD and R(ˆh) be the corresponding expected loss, so our target is to upper bound the generalization error R(ˆh) - ˆRρ(ˆh).

Theorem 1. Assume that ∀x ∈ X, ‖x‖ ≤ b. Let p and u be the sizes of positive set and unlabeled set respectively, α, β be the trade-off parameters in (2), and ˆh be the scoring function learned by the proposed algorithm. For any δ ≥ 0, with probability at least 1 - δ, we have

Before proving this theorem, we first present some useful definitions and lemmas.

Definition 2. (Rademacher complexity, [Bartlett and Mendelson, 2002]) Let σ = {σ1, . . . , σn} be a set of independent Rademacher variables which are uniformly sampled from {-1, 1}. Let v1, . . . , vn be an independent distributed sample set and F be a function class. The Rademacher complexity is defined as:

Lemma 3. (Generalization bound, [Bartlett and Mendelson, 2002]) Let F be a [0, 1]-valued function class on X and f ∈ F. Given x1, . . . , xn ∈ X are i.i.d. variables, then for any δ > 0, with probability at least 1 - δ, we have

The Rademacher complexity appeared in (28) can be bounded by the following Lemma, which is

Lemma 4. (Talagrand contraction Lemma, [Bartlett and Mendelson, 2002]) If L : R → R is Lipschitz continuous with constant L and satisfies L(0) = 0, then

where "◦" represents the composition of two functions.

Now we present the formal proof for Theorem 1:

Proof. Let H1 be the family of hypothesis mapping X ×Y to R defined by H1 = {(x, y) ↦→ ρh (x, y) : h ∈ H}. By Lemma 3, with probability at least 1 - δ, for all h ∈ H, we have

Since 1t≤0 ≤ ℓ(t) for all t ∈ R, the expected error R(h) is the lower bound of E [ℓ (ρh (x, y))], namely R(h) = E[1[h(x,y)-h(x,y′ )]≤0] ≤ E [ℓ (ρh (x, y))], and thus we have

where

and

To upper bound the Rademacher complexities in (32) and (33), we first derive an upper bound for the classifiers in H. Due to the optimality of any classifier parameters ω, we have

when ω is set to 0. Since each term in (34) is nonnegative, we can get an upper bound for ‖ω‖2 , which implys that ‖ω‖2 ≤ 2α + 2β.

Now we are going to bound Rp(ℓρ(p) ◦H1) and Ru(ℓρ(u) ◦ H1). Specially, since the function ℓ(x) is 1/ρ-Lipschitiz, by using Lemma 4, we have Rp(ℓρ(p) ◦ H1) ≤ Rp(H1)/ρ(p) and Ru(ℓρ(u) ◦ H1) ≤ Ru(H1)/ρ(u). For any family of hypothesis mapping h : X ×Y → R, we define Π1(H) = {x ↦→ h(x, y) : y ∈ Y, h ∈ H}. Based on the theorem 8.1 in [Mohri et al., 2018], we can directly get the upper bounds for Rp(H1) and Ru(H1), which are Rp(H1) ≤ 4Rp(Π1(H)) and Ru(H1) ≤ 4Ru(Π1(H)). Next we are going to upper bound Rp(Π1(H)) and Ru(Π1(H)). By noting that E[σiσj ] = 0 for i ̸= j, we have

where the Inequality 1 holds because of the Jensen's Inequality and the concave property of the square-root function.

Similarly, we have

By combining the formulation (31) and the upper bound for (32) and (33), it is easy to get that for any learned classifier ˆh, with probability at least 1 - δ, we have

which concludes the proof of Theorem 1.

Theorem 1 shows that by either increasing the sample size of positive or unlabeled data, the generalization error bound of PULD decreases, which justifies the usefulness of positive and unlabeled data in PU learning. This also guarantees the generalization ability of the proposed learning algorithm.

4 Experiments

To demonstrate the superiority of our proposed PULD to the existing PU methods, we perform intensive experiments on both benchmark and real-world datasets in this section.

4.1 Benchmark Datasets

In this section, we compare our PULD with state-ofthe-art PU learning algorithms such as Weighted SVM (WSVM) [Elkan and Noto, 2008], Unbiased PU risk [Du Plessis et al., 2015], Non-Negative PU risk (NNPU) [Kiryo et al., 2017], and Loss Decomposition and Centroid Estimation (LDCE) [Shi et al., 2018] on OpenML 1 benchmark datasets. Specifically, five binary datasets are adopted for algorithm evaluation including vote, diabetes, wdbc, fri, and phishing, and their configurations are listed in Table 1.

For each dataset, we randomly choose r = 20%, 30%, and 40% positive examples as well as all negative examples as unlabeled and leave the rest positive examples as labeled. Under each r, we conduct five-fold cross validation on every compared method and report the average accuracy over the five independent implementations. Note that all data features have been normalized in advance, and the selected positive examples and the dataset splits are kept identical for all compared methods. In our experiments, the proportion of positive examples in unlabeled set c is assumed to be known during training for all the compared methods, which is also assumed by the existing PU learning works such as [Du Plessis et al., 2015; Kiryo et al., 2017; Shi et al., 2018]. Practically, it can be efficiently estimated by the methods such as [Liu and Tao, 2016; Christoffel et al., 2016]. The parameters of every algorithm have been carefully tuned on the validation set to achieve the best performance. To be specific, the parameter β of NNPU is tuned to the default value 0 on all benchmark datasets. For LDCE, we choose regularization parameter λ from {2-4 , . . . , 24 } and β from {0.1, 0.2, . . . , 0.9} according to [Shi et al., 2018]. Moreover, for the proposed PULD, K is chosen from the candidate set {6, 8, 10, 12, 14}, δ is chosen from {10-2 , . . . , 101 }, and the trade-off parameters µ, γ, and λ in (10) are turned by searching the grid {10-4 , . . . , 101 }. Furthermore, we also adopt the t-test with significance level 0.05 to investigate whether our PULD is significantly better than other baselines.

The test accuracies of all methods on the five benchmark datasets are reported in Table 1. We can find that PULD generally achieves the best classification accuracy compared with the baselines. Besides, the accuracies obtained by PULD on the five datasets are all above 75%, which suggests that PULD generates very impressive classification results although it is trained without negative data.

4.2 Real-world Datasets

Here we investigate the performance of WSVM, UPU, NNPU, LDCE, and PULD on the practical image classification task, and CIFAR-10 [Krizhevsky and Hinton, 2009] and SVHN [Netzer et al., 2011] datasets are chosen to test their performance. CIFAR-10 consists of 60000 32×32 natural images in 10 classes with each class containing 6000 images. We choose the images of 'airplane', 'auto mobile', 'ship', and 'truck' as negative, and regard the images of 'bird', 'cat', 'deer', 'dog', 'frog', and 'horse' as positive. Therefore, there are 24000 positive examples and 36000 negative examples. SVHN contains 99289 32×32 digit images belonging to 10 classes, i.e. the digits '0'-'9', where the negative set is formed by the digit images '1'-'5', and the rest digit images compose the positive set. As a result, we get 34699 positive examples and 64590 negative examples.

1 https://www.openml.org/

In our experiment, we extract the 512-dimensional GIST features for each image. Similar to the above experiments, for each image dataset, the situations of r = 20%, 30%, and 40% are particularly studied. Note that the training set and the test set are split in advance with 50000 training examples and 10000 test examples for CIFAR-10, and 73257 training examples and 26032 test examples for SVHN. The test accuracies achieved by the compared methods on the two datasets are presented in Table 2, where we can clearly see that our PULD achieves the highest classification accuracy among all comparators on both CIFAR-10 and SVHN. Therefore, the proposed PULD is effective in handling real-world data.

4.3 Parametric Sensitivity

The model (10) of our PULD contains three trade-off parameters µ, γ, and λ. Therefore, this section examines the parametric sensitivity of our model to them. The two real-world datasets CIFAR-10 and SVHN are adopted here. Figure 1

shows the test accuracies of our method on these two datasets when r=20%. We change µ from 10-3 to 100 , and γ and λ from 10-4 to 10-1 . From Figure 1, we observe that the three parameters have very slight effect on the accuracy, therefore they can be easily tuned for practical implementations.

5 Conclusion

This paper proposed a novel PU learning algorithm named "Positive and Unlabeled learning with Label Disambiguation" (PULD). Specifically, we convert PU learning to a partial label learning problem, and use the disambiguation technique to efficiently identify the ground-truth labels. The proposed model can be easily solved via an alternative optimization process, and its generalization bound has also been theoretically proved. The experimental results on both benchmark and real-world datasets clearly show that PULD is superior to the state-of-the-art PU methods.

Acknowledgments

This research is supported by NSF of China (Nos: 61602246, U1713208), NSF of Jiangsu Province (No: BK20171430), the Fundamental Research Funds for the Central Universities (No: 30918011319), the Summit of the Six Top Talents Program (No: DZXX-027), the Innovative and Entrepreneurial Doctor Program of Jiangsu Province, the Young Elite Scientists Sponsorship Program by Jiangsu Province, the Young Elite Scientists Sponsorship Program by CAST (No: 2018QNRC001), the Australian Research Council Projects (Nos: DP-180103424, DE-1901014738), and Program for Changjiang Scholars.