Posistive-Unlabeled Learning via Optimal Transport and Margin Distribution

1 Introduction

In ordinary supervised learning, training a classifier usually requires labeled instances from all classes, which may be impractical or need additional steps which will incur unaffordable cost in many real-world scenarios. For example, in personalized advertising tasks, the pages that are visited and clicked by the user can be treated as positive instances. However, the rest huge amount of unexplored pages may not be uninteresting, thus they can not be simply labeled as negative instances. Such problems lead to the research of positive-unlabeled (PU) learning [Elkan and Noto, 2008; Bekker and Davis, 2020], where training a classifier can only access a portion of positive instances while the remaining unlabeled data could be either positive or negative.

Due to the importance of such framework, it has attracted lots of interest from the machine learning community. So far, the development of PU learning can be roughly classified into three stages. The algorithms in the first stage [Liu et al., 2002; Li and Liu, 2003; Tao et al., 2008; Chaudhari and Shevade, 2012] take the separability and smoothness assumptions, and adopt a two-step strategy in which reliable negative instances are identified first, followed by a traditional (semi)- supervised learning approach. The algorithms in the second stage [Mordelet and Jean Philippe, 2014; Shao et al., 2015; Du Plessis et al., 2015b] directly treat PU learning as a biased learning problem, in which the unlabeled instances are viewed as noisy negative instances. In the last stage, the algorithms [Bekker and Davis, 2017; Kiryo et al., 2017; Zhang et al., 2019; Chang et al., 2021] usually incorporate class prior to learn an unbiased classifier.

∗Contact Author

Existing PU learning algorithms either suffer an overestimation of class prior or simply assume it is given ahead of time. To obtain a more precise class prior, ℓ1 divergence between the positive data and the whole data is employed to penalize the overestimation of class prior [Du Plessis et al., 2015a]. Besides, kernel mean embedding has also been introduced to characterize the matching degree between these two distributions [Chang et al., 2021]. Different from these methods, we explicitly learn a transformation from unlabeled data to positive data by entropy regularized optimal transport (OT) [Kantorovitch, 1958; Frogner et al., 2015; Peyr´e et al., 2019], which brings us a much more precise estimation of class prior. Moreover, most PU learning methods learn the decision boundary through optimizing the minimum margin, which is not suitable in PU learning because it is very sensitive to label noise. In this paper, we optimize the margin distribution (MD) [Zhang and Zhou, 2014], rather than the minimummargin, to obtain a label noise insensitive classifier enjoying much better generalization performance. To summarize, our contributions are

• It achieves a muchmore precise estimation of class prior by leveraging the entropy regularized OT.
• It utilizes the margin distribution optimization to alleviate the inevitable label noise in PU learning.
• It shows significantly better generalization performance on both synthetic and real-world data sets.

The rest of the paper is organized as follows. We first introduce some basic preliminaries, and then present the proposed methods. After that, we detail the optimization procedure, followed by the empirical studies. Finally we conclude the paper with future works.

2 Preliminaries

We first present some notations utilized throughout the paper. The scalars are denoted by normal font letters (e.g., x, X). The boldface letters (e.g., x, X) denote the vectors and matrices respectively. The upper case letters with mathcal font (e.g., S) indicate the sets. In particular, [m] is defined as the integer set {1, 2, . . . ,m}.

Without loss of generality, for PU learning data set S = {(xi, yi)}i∈[p]∪{xj}j∈[m]\[p], we assume the first p instances are positive, i.e., yi = 1 for any i ∈ [p] ≜ P, while the remaining u = m- p instances are unlabeled, i.e., yj is unknown for any j ∈ [m] \ [p] ≜ U. The class prior is denoted by π = P(y = 1) in unlabeled data, and the mixed class-wise unlabeled data density can be formulated as

2.1 Optimal Transport

OT is a useful mathematical tool to evaluate the difference between pairs of probability distributions. It is the cost of transforming the source distribution to the target distribution. It has also been proven to be a well defined distance and can integrate with metric learning [Song et al., 2017] to better exploit the rich geometric structure on the space of probability distributions, which has been applied in many machine learning methods [Ho et al., 2017; Blondel et al., 2018; Titouan et al., 2019]. To make the computation efficient, the entropy regularized version of OT is proposed. It encourages dense transport coefficients and can help distinguish the instances sampling from different class distributions.

As shown in Figure 1(a), dots and crosses are from two class distributions. We randomly choose some red crosses as empirical target distributions and the rest with all dots as empirical source distributions, then utilize entropy regularized OT to transport source to target. In Figure 1(b), we connect the source instance with the target instance for which the largest transport coefficient exceeds the prespecified threshold. It can be seen that the blue crosses are connected with the red crosses while the blue dots are not. Thus we can identify the underlying crosses by checking the largest transport coefficient.

2.2 Optimal Margin Distribution Learning

Margin is one of the most essential concepts in machine learning. It indicates the confidence of the prediction results. Recent studies on margin theory [Gao and Zhou, 2013] demonstrate that margin distribution is crucial to generalization, and gives rise to a novel statistical learning framework named optimal margin distribution machine (ODM) [Zhang and Zhou, 2019]:

where γ(xi, yi) is the margin of xi, ¯ γ is the margin mean, α and β are trading-off hyperparameters. The first regularization term ∥w∥2 /2 controls the model complexity. The summation of slack variables ξi and ϵi in the last term is exactly the margin variance.

ᇱ

୬୧୫݄ ୱ୧ୢ݄

ୱ୧ୢ݄

ᇱ

మ୬୧୫݄

Since more stable performance than the minimum margin based counterparts, ODM has been extended to many general learning settings [Zhang and Zhou, 2017; Zhang and Zhou, 2018a; Zhang and Zhou, 2018b; Zhang et al., 2020; Zhang and Jin, 2021; Cao et al., 2021]. Figure 2 illustrates the differences between ODM and SVM when solving the supervised and PU learning tasks respectively. For supervised learning, both hmin and hdis achieve good performance. However, for PU learning, optimizing minimum margin only focuses on a small proportion of instances, which may result in multiple low-density decision boundaries, e.g., h′min1 and h′min2 , and a wrong selection will lead to a degenerated performance. Meanwhile, optimizing the whole margin distribution can help us avoid such a dilemma.

3 Class Prior Estimation by Regularized OT

The proposed estimation algorithm consists of two steps. In the first step, we utilize entropy regularized OT to identify the possible positive and negative instances in unlabeled data. Specifically, we treat positive instances as empirical target distribution pt, while unlabeled instances as empirical source distribution ps. All instances are assigned with equal mass density. Assume C = [Cij]u×p is the cost matrix with the (i, j)-th entry Cij = exp(-∥xi-xj∥2/2δ2 ) indicating the cost of transporting one unit mass from [ps]i to [pt]j, where δ is the width hyperparameter. Then the transportation from unlabeled instances to positive instances with minimum cost can be formalized as:

where T = [Tij ]u×p is the optimal transport matrix, Ω(T) = - ∑ij Tij(log Tij -1) is the entropy regularization term, and η is the trading-off hyperparameter. The problem of Eq. (2) have already been well studied and the unique solution can be obtained by the Sinkhorn-Knopp algorithm [Cuturi, 2013]. When we obtain transport matrix T, we set a threshold σ to identify the reliable instances. Specifically, for each unlabeled instance xi, we treat it as a candidate positive instance if the maximal transport coefficient maxj Tij ≥ σ, and vice versa. The intuition is that the underlying positive instances of unlabeled set and the positive data share the same distribution, thus the most likely positive instances will be firstly and concentratedly transported to the nearest positive instances.

In the second step, we utilize the discovered possible positive and negative instances to estimate the class prior. For PU learning, the distribution of unlabeled data can be approximately represented by a convex combination of positive and negative distributions as Eq. (1). Suppose the candidate positive instances are {xj | j ∈ Cp} and the candidate negative instances are {xk | k ∈ Cn}. Then the class prior π can be estimated by minimizing the following distance between the unlabeled instance mean and the mixture of candidate positive and negative instance mean:

Eq. (3) can also be optimized in some reproducing kernel Hilbert space (RKHS), i.e., all instances are embedded to this RKHS first via the inducing kernel mapping ϕ(·), and then minimize the distance in this new feature space. In addition, Eq. (3) is a convex quadratic programming (QP), which can be easily solved via off-the-shelf QP solvers. The overall optimization procedure is summarized in Alg. 1. It is worth noting that we also return the candidate labels y(0) u for unlabeled instances to initialize the later optimization procedure.

4 Training withMargin Distribution

In this section, we detail the training of classifier.

4.1 ProposedMethod

We first build a kNN-based graph G(V, E), where V is the vertex set consisted of instances in S, and E is the edge set representing the similarity between pairs of instances. We utilize G(V, E) to exploit the relation between feature space and label space, and identify the ground-truth labels. We denote A = [Aij]m×m as adjacency matrix of G(V, E), and Aij = exp(∥xi-xj∥2/2δ2 ) if xi and xi are linked, and Aij = 0 otherwise, and ¯A = D-1/2AD-1/2 as normalized adjacency matrix, where Dii = ∑j Aij . We use ¯A to exploit relations between instances, and obtain:

Algorithm 1 Class prior estimation

• 1: Input: PU data set S, regularization hyperparameter η, threshold σ.
• 2: Calculate the cost matrix C.
• 3: Obtain T by solving Eq. (2).
• 4: Find the candidate instances in unlabeled data.
• 5: Calculate the class prior ˆπ by solving Eq. (3).
• 6: Output: class prior ˆπ, candidate labels y(0) u .

where only {yi}i∈U are optimization variables while {yi}i∈P are fixed, {αi}i∈P and {αi}i∈U indicate trade-off parameters for labeled and unlabeled data, I(·) is the indicator function. In the above formulation, the second term as well as the Eq. (4) restrict margin variance of labeled positive instances, Eq. (5) imposes on the unlabeled instances to be accurately classified with less margin deviations. The final term is a smooth regularization letting the similar instances be more likely to have similar labels. Moreover, the final constraint ensures a proportion ˆπ of unlabeled instances to be positive.

4.2 Optimizing Classifier

If the labels of unlabeled data are available, our method reduces to the binary classification ODM [Zhang and Zhou, 2019]. Furthermore, because y is integer variable, it is difficult to optimize it together with w, ξ, ϵ. Thus we resort to the alternating optimization method.

Notice that y appears both in the objective function and the constraints, which makes the optimization difficult. To handle this problem, we apply the variable splitting technique by introducing an auxiliary variable q = [q1, . . . , qm], and Eq. (4) becomes

where the last term is set to make y and q as similar as possible and λ is a balancing parameter. Then, we need to solve the three subproblems in terms of w, y, and q respectively.

Optimizing w. Fixing ξ, ϵ, y and q, we have

Notice that the Eq. (7) is a convex quadratic programming (QP), which can be easily solved via off-the-shelf QP solvers.

Optimizing ξ, ϵ and y. Fixing w and q, we have

First we denote ξi,yi = max(0, 1 - θ - yiw⊤ϕ(xi)), ϵi,yi = max(0, yiw⊤ϕ(xi) - 1 - θ), and li,yi = ξ 2 i,yi +µϵ2i,yi , then we define the cost matrix B = [Bij]m×2 to distinguish the loss of positive and unlabeled data. For positive data, we set the i-th row [Bi1, Bi2] = [E, li,1] where E is a large constant such as 103 specified in advance, while for unlabeled data, we set [Bi1,Bi2] = [li,-1, li,1]. Furthermore, we denote Y = [Yij]m×2 as the one-hot encoding of y. We also define Q = [Qij]m×2 in the same way. Then Eq. (8) can be rewritten as

Eq. (9) can be converted to a linear programming (LP) by relaxing Yij ∈ {0, 1} as Yij ∈ [0, 1] and solved by off-theshelf LP solvers. Then the optimal yi can be set as 1 if Yi1 < Yi2 and -1 otherwise.

Optimizing q. Fixing w, ξ, ϵ and y, we have:

Notice that the indicator function is discontinuous and difficult to optimize, we use ℓ2 norm as a surrogate, and we have:

The closed form solution of Eq. (10) is

We can obtain qi according to Qij in a similar way as yi. Alg. 2 shows the whole optimization procedures.

5 Experiments

In this section, we empirically show the effectiveness of our proposed method.

5.1 Data Sets and Settings

We perform experiments on both synthetic and real-world data sets. For real-world data sets, we utilize eight data sets from the UCI Machine Learning Repository. Their basic statistics are listed in Table 1.

Algorithm 2 Classifier training

• 1: Input: PU data set S, kNN based graph G(V, E), ODM hyperparameters µ, θ, αi, trading-off hyperparameters λ, τ, estimated class prior ˆπ, maximum iteration number T .
• 2: Initialize: t = 0, w = 0, yu = qu = y(0) u , [Bi,1,Bi,2] = [E, 0] for any i ∈ P, [Bi,1,Bi,2] = [1/2, 1/2] for any i ∈ U.
• 3: while t < T and not converge do
• 4: Update w, ξ and ϵ by fixing Y, Q and solve Eq. (7).
• 5: Update coefficient matrix B.
• 6: Update Y and Q by solving Eq. (9) and Eq. (10).
• 7: if converge then
• 8: Break.
• 9: end if
• 10: end while
• 11: Output: w.

For synthetic data sets, we construct two Gaussian distributions centers set at (0, 0) and (3, 3), and the covariance matrixes of them are set to [ 1 0 0 1 ] and [ 1 -0.8 -0.8 1 ]. It contains 400 labeled positive instances and 1000 unlabeled instances.

To demonstrate the superiority of our proposed PUOTMD, we compare it with three PU learning methods which also integrate class prior estimation algorithms EN [Elkan and Noto, 2008], PE [Du Plessis Marthinus and Sugiyama, 2014], and CAPU [Chang et al., 2021], and six more PU learning methods WLR [Lee and Liu, 2003], PULD [Zhang et al., 2019], UPU [Du Plessis et al., 2015b], nnPU [Kiryo et al., 2017], PUSB [Kato et al., 2018], and LDCE [Shi et al., 2018], which adopt different strategies to deal with PU learning problems and they all require a precisely given class prior to train the classifiers. The experiments are conducted with class prior from {0.3, 0.5, 0.7}. All data sets are randomly divided into training and test set with ratio 7:3, and we randomly select labeled and unlabeled instances according to select completely at random (SCAR) assumption [Bekker and Davis, 2020], i.e., the labeled instances are i.i.d. sampled from positive data distribution. We repeat the experiments ten times and record the average value and standard deviations of performance.

All hyperparameters of the baselines are tuned in the same way reported in the references. For CAPU and LDCE, their two trade-off hyperparameters are tuned from {2-5 , . . . , 25 } and {10-3 , . . . , 103 } respectively. The balancing hyperparameters in PULD are tuned from {10-3 , . . . , 103 }. As for our proposed method, we set the number of nearest neighbors N = 10, and the width of RBF kernel is selected from {2-10 , 2-9 , . . . , 23 }. We tune ODM hyperparameters µ and θ from the set {0.1, 0.2, . . . , 0.9}, the threshold σ is set as min{1, 10/p}, and the balancing hyperparameters are selected from {10-3 , . . . , 103 }.

5.2 Results

We first compare it with three PU learning methods EN, PE, and CAPU on synthetic data sets without giving class prior. The results are shown in Table 2. It can be seen that when class prior is 0.3 and 0.5, PUOTMD not only achieves a more precise class prior estimation but also produces a better classifier. When class prior is 0.7, PUOTMD only loses to CAPU in terms of class prior estimation, but still achieves the best classification accuracy.

We also conduct experiments on real-world data sets. Again we compare it with EN, PE, and CAPU without providing class prior. The results are shown in Table 3. It can be seen that EN is very prone to overestimate the class prior and thus getting the worst performance among the baselines. Our proposed PUOTMD achieves a more accurate class prior, which verifies the effectiveness of our proposed entropy regularized OT estimation method. Moreover, it outperforms other baselines on Diabetes in all class prior settings. In most cases, PUOTMD achieves both better class prior estimation and classification accuracy, but under the circumstance of less accurate estimation of class prior, PUOTMD can also achieve better classification accuracy, e.g., on House when class prior is 0.7.

Table 4 exhibits the classification accuracy of nine methods on eight data sets with given class priors. It can be seen that on Banknote, Spambase, and Musk, PUOTMD outperforms other methods in all class prior settings, and on other data sets, PUOTMD also performs better in most cases. Compared to PULD and EN, which adopt minimum margin framework, PUOTMD wins on Diabetes and Australian under all class prior settings, while on other data sets, it performs significantly better than EN in almost all the class prior settings, and beats PULD when class prior is 0.7. These verify that PUOTMD possesses better generalization performance than the minimum margin based PU learning methods. As for other baselines, PUOTMD only loses to CAPU in Diabetes when class prior is 0.3, and performs significantly better in most cases.

From the above experimental results, we can see that, in general, PU learning tasks where class prior is not given, our entropy regularized OT method estimates class prior more accurately, and achieves better classification performance. When class prior is available, our PUOTMD gets better classification accuracy in most cases, and shows better generalization performance than minimum margin based methods.

6 Conclusions

In this paper, we propose a novel PU learning method named PUOTMD, which consists of estimating class priors and training classifiers. Specifically, we first leverage the entropy regularized OT to adaptively discover the reliable positive and negative instances in unlabeled data, then utilize the mixture proportion estimation to produce an accurate class prior. Next, we jointly optimize the margin distribution and the labels of unlabeled data. Finally, we perform extensive experiments to verify its superiority. In the future, we will conduct theoretical analysis on our proposed method.

Acknowledgments

This work was supported in part by the National Key R&D Program of China under Grant 2020AAA0108501, the National Natural Science Foundation of China under Grant 62006088 and the Key R&D Program of Hubei under Grant 2020BAA020.