Year: 2022

Abstract:
Given only positive (P) and unlabeled (U) data, PU learning can train a binary classifier without any negative data. It has two building blocks: PU class-prior estimation (CPE) and PU classification; the latter has been well studied while the former has received less attention. Hitherto, the distributional-assumption-free CPE methods rely on a critical assumption that the support of the positive data distribution cannot be contained in the support of the negative data distribution. If this is violated, those CPE methods will systematically overestimate the class prior; it is even worse that we cannot verify the assumption based on the data. In this paper, we rethink CPE for PU learning—can we remove the assumption to make CPE always valid? We show an affirmative answer by proposing Regrouping CPE (ReCPE) that builds an auxiliary probability distribution such that the support of the positive data distribution is never contained in the support of the negative data distribution. ReCPE can work with any CPE method by treating it as the base method. Theoretically, ReCPE does not affect its base if the assumption already holds for the original probability distribution; otherwise, it reduces the positive bias of its base. Empirically, ReCPE improves all state-of-the-art CPE methods on various datasets, implying that the assumption has indeed been violated here.

heading: 1 INTRODUCTION
text: Positive-unlabeled (PU) learning can date back to 1990s (Denis, 1998; De Comité et al., 1999; Letouzey et al., 2000), and there has been a surge of interest in this learning scenario in recent years because of the difficulty to annotate large-scale datasets (Ren et al., 2014; du Plessis et al., 2014; 2015; Christoffel et al., 2016; Jain et al., 2016; Ramaswamy et al., 2016; Sakai et al., 2018; Kato et al., 2018; Bekker & Davis, 2018; Gong et al., 2019; Bai et al., 2021; Xia et al., 2021; Yao et al., 2021). It is also fallen into different applications, such as knowledge-base completion (Galárraga et al., 2015; Neelakantan et al., 2015), text classification (Lee & Liu, 2003; Li & Liu, 2003), and medical diagnosis (Claesen et al., 2015; Zuluaga et al., 2011).
PU learning can be divided into two different settings based on different data generation processes. The first setting is called censoring PU learning (Elkan & Noto, 2008), which follows a one-sample configuration. Specifically, a sample S is randomly drawn from the unlabeled data distribution Pu, and a positive sample Sp is then distilled from it, i.e., randomly selecting some positive instances contained in the unlabeled data to be the positive sample. The second setting is called case-control PU learning (Kiryo et al., 2017). In this setting, a positive sample Sp = {xi}ki=1 is randomly drawn from the positive class-conditional distribution Pp = P (X|Y = 1), and an unlabeled sample Su = {xi}ni=k+1 is randomly drawn from the unlabeled data distribution Pu. Because case-control PU learning is more general than censoring PU learning (Niu et al., 2016), therefore, we will focus on the setting of case-control PU learning.
Under the setting of case-control PU learning, a lot of classification methods have been proposed (Ren et al., 2014; du Plessis et al., 2014; 2015; Christoffel et al., 2016; Sakai et al., 2018; Kato et al., 2018; Bekker & Davis, 2018; Kwon et al., 2019; Tanielian & Vasile, 2019; Gong et al., 2019).
†Correspondence to Tongliang Liu (tongliang.liu@sydney.edu.au).
However, the class-prior estimation (CPE) (Elkan & Noto, 2008; Jain et al., 2016; Ramaswamy et al., 2016; Christoffel et al., 2016; Kato et al., 2018) has received less attention. Formally, CPE is defined as a problem of estimating π = P (y = 1) ∈ (0, 1) given a sample from the marginal distribution Pu and a sample from positive class-conditional distribution Pp. The marginal distribution Pu is mixed with both positive and negative class-conditional distributions, i.e., Pu = πPp+(1−π)Pn. CPE acts as a crucial building block for state-of-the-art PU classification methods, and it is essential to build statistically-consistent PU classifiers (du Plessis et al., 2014; Scott, 2015; Jain et al., 2016; Kiryo et al., 2017). The formulation of these classification methods involves the class-prior π, but π is usually unknown in practice. If π is poorly estimated, the classification accuracy of the state-of-the-art PU classification methods (du Plessis et al., 2014; 2015; Kiryo et al., 2017) could be degraded.
The mixture proportion estimation (MPE) is closely related to CPE (Blanchard et al., 2010; Scott, 2015). In the setting of MPE, there is a mixture distribution
F = (1− κ∗)G+ κ∗H, (1)
where H and G are called component distributions. Given the samples randomly drawn from F and H , respectively, MPE aims to estimate the maximum proportion κ∗ ∈ (0, 1) of H in F . Thereby, if the maximum proportion κ∗ is identical to the class-prior π, the MPE methods can be employed to obtain π by letting Pu and Pp be the mixture distribution F and the component distribution H , respectively; otherwise, the MPE methods cannot be employed. To the best of our knowledge, most of state-of-the-art CPE methods (Blanchard et al., 2010; Liu & Tao, 2015; Scott, 2015; Ramaswamy et al., 2016; Jain et al., 2016) are based on MPE, which do not rely on assumptions that the data are drawn from a given parametric family of probability distributions (i.e., they are distributional-assumption-free methods).
To let these distributional-assumption-free methods can be used to identify class-prior π, κ∗ must be identical to the class-prior π. The irreducibility assumption (Blanchard et al., 2010) has been proposed to make them identical, which is employed by all these CPE methods implicitly or explicitly, to the best of our knowledge. It assumes that the support of the positive class-conditional distribution Pp is not contained in the support of the negative class-conditional distribution Pn. However, it is strong and hard to be verified in PU learning, since Pn is a latent distribution, such that we do not have any prior knowledge about it. Additionally, since the applications of PU learning are diverse (Hsieh et al., 2019; Bekker & Davis, 2020), it is hard to guarantee that the support of Pp is not in the support of Pn.
If the irreducibility assumption cannot be satisfied, the existing distributional-assumption-free CPE methods will suffer from an overestimation of π. For example, in Figure 1(a), we show both the unlabeled data distribution Pu and the component distribution Pp. In Figure 1(b), we assume the latent negative class-conditional distribution Pn is fixed as shown in the green color, and the positive class-prior π = 0.5. In Figure 1(c), we show the existing distributional-assumption-free CPE methods will output the biased class-prior 0.7. It is different from the ground truth 0.5, since the support of Pp is contained in the support of Pn. When the irreducibility assumption is not held, how to improve the estimations of distributional-assumption-free PU learning methods is challenging but useful.
Because the irreducibility assumption is impossible to check without making any assumption on Pn. Thereby, in this paper, we rethink those CPE methods and propose a novel method called Regrouping CPE (ReCPE) which improves the estimations of the current PU learning methods without irreducibility assumption. The main idea of our method is that, instead of estimating the maximum proportion of Pp in Pu, we build a new CPE problem by creating a new auxiliary distribution Pp′ always guaranteeing the irreducibility assumption. Then we use the existing CPE method to obtain the maximum proportion of Pp′ in Pu, which is denoted by π′. We show that, with both theoretical analyses and experimental validations, when the irreducibility assumption holds, our ReCPE method does not affect the prediction of the existing estimators; when the irreducibility assumption does not hold, our method will help the current estimators have less estimation bias, which could improve the performances of PU classification tasks. For example, in Figure 1(d), we create a new class-conditional (auxiliary) distribution Pp′ . By solving it, π′ = 0.51. The estimation bias of the existing estimators will reduce to π′ − π = 0.01 instead of κ∗ − π = 0.2. The rest of the paper is organized as follows. In Section 2, we review the irreducibility assumption and its variants. We discuss the difficulty of checking the assumptions. In Section 3, we provide the estimation biases of the existing consistent distributional-assumption-free CPE methods. Then we propose our method ReCPE, followed by theoretically analysis of its estimation bias and the implementation details. All the proofs are listed in Appendix A. The experimental validations are given in Section 4. Section 5 concludes the paper.

heading: 2 IRREDUCIBILITY OF CPE
text: In this section, we briefly review the assumptions used for existing distributional-assumption-free CPE estimators. Then we provide the estimation bias introduced by consistent distributional-assumptionfree CPE methods when the assumptions do not hold.
The irreducibility assumption. Let Pp and Pu be probability measures (distributions) on a measurable space (X ,S), where X is the sample space, and S is the σ-algebra. Let κ∗ be the maximum proportion of Pp in Pu. To let κ∗ be identical to π, the irreducibility assumption was proposed by Blanchard et al. (2010). Definition 1 (Irreducibility). Pn and Pp are said to satisfy the irreducibility assumption if Pn is not a mixture containing Pp. That is, there does not exist a decomposition Pn = (1− β)Q+ βPp, where Q is a probability distribution on the measurable space (X ,S), and 0 < β ≤ 1.
Equivalently, the assumption assumes the support of Pp is hardly contained in the support of Pn. It means that with the selection of different sets S, the probability Pn(S) can be arbitrarily close to 0, and Pp(S) > 0. Suppose we can access the distributions Pu, Pp and the set C containing all possible latent distributions, then the class-prior π can be found as follows:
π = κ∗ , sup{α|Pu = (1− α)K + αPp,K ∈ C} = inf S∈S,Pp(S)>0
Pu(S) Pp(S) . (2)
To the best of our knowledge, all existing distributional-assumption-free CPE methods (Blanchard et al., 2010; Scott et al., 2013; Liu & Tao, 2015; Scott, 2015; Ramaswamy et al., 2016; Ivanov, 2019) are variants of estimating the maximum proportion κ∗ of Pp in Pu. Many of them are statistically consistent estimators (Blanchard et al., 2010; Scott et al., 2013; Liu & Tao, 2015; Scott, 2015).
The variants of the irreducibility. Based on the irreducibility assumption, estimators can be designed with theoretical guarantees that they will converge to the class-prior π (Blanchard et al., 2010). However, the convergence rate can be arbitrarily slow (Scott, 2015). The reason is that the irreducibility assumption implies the following fact (Blanchard et al., 2010; Scott et al., 2013)
inf S∈S,Pp(S)>0
Pn(S) Pp(S) = 0, (3)
i.e., the maximum proportion of Pp in Pn approaches to 0. To obtain the class-prior π, it requires finding a sequence of the sets S converging to the infimum, which empirically can be hard to find. Therefore, the convergence rate of the designed estimators based on Eq. (3) will be arbitrarily slow. To ensure a fixed rate of convergence, the anchor set assumption, a stronger variant of the irreducibility
assumption, has been proposed (Scott, 2015; Liu & Tao, 2015; Xia et al., 2019; 2020; Yao et al., 2020). It assumes that
min S∈S,Pp(S)>0
Pn(S) Pp(S) = 0, (4)
i.e., there exists a set can achieve the minimum 0, which is called an anchor set. Another stronger variant is the separability assumption (Ramaswamy et al., 2016) which extends the anchor set assumption to a function space. It is proposed to bound the convergence rate of the method based on kernel-mean-matching (KMM) technique (Gretton et al., 2012).

heading: 3 REGROUPING FOR CPE (RECPE)
text: In this section, we propose a general method named regrouping for CPE (ReCPE). We discuss how to theoretically and empirically mitigate the overestimation problem of the class-prior π.

heading: 3.1 MOTIVATION
text: In general, it is impossible to verify the irreducibility assumption for CPE. To check the assumption, we need to make Pn itself to be observable and verify that whether the distribution Pn is a mixture containing the distribution Pp, which obviously contradicts the setting of PU learning. However, in practice, the irreducibility assumption may not hold for many real-world problems, because the negative class is diverse (Hsieh et al., 2019; Bekker & Davis, 2020) in PU learning. If the assumption does not hold, Pn is said to be reducible to Pp, and distributional-assumption-free CPE methods will introduce an estimation bias. Proposition 1. Let β∗ = infS∈S,Pp(S)>0 Pn(S) Pp(S)
be the maximum proportion of Pp in Pn, given Pu = (1− π)Pn + πPp, for 0 < π ≤ 1, we have
κ∗ = π + (1− π) inf S∈S,Pp(S)>0
Pn(S) Pp(S) = π + (1− π)β∗. (5)
According to Proposition 1, if the irreducibility assumption does not hold, then there exists β > 0. In this case, maximum proportion κ∗ can still be obtained, but it is different from π but equal to π + (1 − π)β∗. In this case, if we directly employ existing distributional-assumption-free CPE methods, they could introduce an arbitrary estimation bias (1− π)β∗ which depends on Pn. To reduce the estimation bias, we propose ReCPE. The process of regrouping is to change the original class-conditional distributions Pn and Pp into new class-conditional distributions Pn′ and Pp′ by transporting the probability mass of the set A from the negative class to the positive class. After regrouping, new class-conditional distributions are guaranteed to satisfy the irreducibility assumption, and therefore, the new positive class-prior π′ can be identified by current CPE methods. To get the intuition, we provide a concrete example as follows.
Suppose that Pp is the uniform on [ 12 , 1], Pn is uniform on [0, 1], and π = 1 2 . Then we have Pu such that it is uniform on [0, 12 ) and [ 1 2 , 1], respectively. Specifically, the probabilities are
Pu
( [0, 1
2 )
) = 1
4 , Pu
( [ 1
2 , 1]
) = 3
4 .
In this case, by Eq. 5, the maximum proportion of Pp in Pu is π∗ = 34 . Let ρ > 0 be a small constant and let A = (1− ρ, 1]. In this case, the mass of A in Pu from Pn is πPn(A) = ρ2 . After transporting the mass ρ2 from Pn to Pp, we have a new positive class-prior π
′ and a new class-conditional Pp′ which is uniform on [ 12 , 1− ρ) and [1− ρ, 1], respectively. Specifically,
π′ = 1 + ρ
2 , Pp′
( [ 1
2 , 1− ρ)
) =
1− 2ρ 1 + ρ , Pp′ ([1− ρ, 1]) = 3ρ 1 + ρ .
The left equation above shows that the new class-prior π′ is dependent on ρ or the size of A. By controlling set A or ρ to be small, π′ can be as close to π as possible. This is the intuition of how regrouping works.
Algorithm 1 ReCPE Input: An unlabeled sample Su i.i.d. drawn from Pu, a positive sample Sp i.i.d. drawn from Pp, and the percentage p of the sample needed to copy from Su to Sp.
1: Train a binary classifier h with the unlabeled sample Su and positive sample Sp by treating Su as a negative sample; 2: Assign each example x ∈ Su with the negative class-posterior probability P (Y = −1|X = x) predicted by the trained classifier h; 3: Obtain Sp′ by copying p× |Su| examples with the smallest negative class-posterior probability P (Y = −1|X = x) from Su to Sp; 4: Estimate the class-prior π′ by employing an algorithm based on Eq. (5) with inputs Su and Sp′ . Output: The estimated new class-prior π̂′.

heading: 3.2 PRACTICAL IMPLEMENTATION
text: In practice, we have to implement the aforementioned idea of regrouping based on positive sample Sp and unlabeled sample Su. Since the negative sample is unavailable, we cannot “cut and paste” any example from negative class to positive sample Sp; instead, we can “copy and past” some unlabeled examples to Sp. When doing so, we should select a small set of samples Â∗ which look the most similar to the positive class and dissimilar to the negative class, which could encourage the difference between the original Pn, Pp, and ρ and π, Pp′ , and π′ to be small. This is why Â∗ = (1− ρ, 1] was selected in the above intuitive example, i.e., Â∗ belongs geometrically and visually to the positive class with the highest confidence among all subsets of [0, 1] of size ρ.
A hyper-parameter p ∈ (0, 1) is introduced to control the size of set Â∗, theoretically, we prefer the set Â∗ to have a small size. Empirically, p cannot be so small: the existing estimators are insensitive to tiny modifications (they are designed to be robust in such a way, in order to be good estimators). For example, the difference between the estimated class-priors by employing samples Su and Sp and the one by employing samples Su and Sp′ can be hardly observed if Sp and Sp′ only differ from in one or two points. Specifically, p = 10% is selected for the experiments on all datasets, which leads to a significant improvement of the estimation accuracy. The details on the selection of the hyper-parameter value will be explained in Section 4.1. The algorithm is summarized in Algorithm 1.
There are two fundamental concerns for copying Â∗ to Sp. 1). When we have irreducibility, might regrouping make π̂′ be a worse approximation? 2). When we lack irreducibility, must regrouping make π̂′ be a better approximation? While these concerns will be formally clarified later, we give here intuitive implications of regrouping.
1). If we have irreducibility, the Pn(Â∗) should be rather small (if not zero), and Â∗ should be drawn from the positive component Pp of the mixture Pu. In this case, regrouping will generally have small influence to Pp. Hence, it will not make π̂′ worse.
2). If we lack irreducibility, Â∗ may be drawn from either Pp or Pn. By regrouping, Â∗ becomes present in Sp′ , which encourages the probability of the set Â∗ in Pp′ to be large. This will modify Pp as we expected towards irreducibility. As a consequence, regrouping will make π̂′ better.

heading: 3.3 THEORETICAL JUSTIFICATION
text: In the regrouping approach described above, the auxiliary class-conditional distribution Pp′ and Pn′ are created by regrouping a small set A from Pp and Pn. Here, we analyze the properties of regrouping and theoretically justify it.
A formal definition of regrouping In order to analyze the properties, we need to formally define how to split, transport, and regroup a set A (or the mass of A).
Definition 2. Let M be a probability measure on a measurable space (X ,S). Given a set A ∈ S, we define a measure MA on the σ-algebra S as follows:
∀S ∈ S,MA(S) =M(S ∩A). (6)
It is easy to see that given two measures MA and MA c
obtained according to Definition 2, where Ac = X \A, then MA and MAc have the following property. Lemma 1. Let M be a probability measure over a measurable space (X ,S). For any set A ∈ S, we have MA +MA c =M .
Now, we introduce the theory of regrouping. Fixing a set A ∈ S, we split Pn as PA c n and P A n , transport PAn to Pp to regroup them together, i.e.,
Pu = (1− π)Pn + πPp = (1− π)(PAn + PA c n︸ ︷︷ ︸ split into two ) + πPp = (1− π)PA c n + ((1− π)PAn + πPp︸ ︷︷ ︸ regroup as one ).
Finally, we can rewrite the unlabeled data distribution Pu as a mixture of two new class-conditional distributions Pn′ and Pp′ defined in Theorem 1 by normalization. Theorem 1. Let Pu = (1− π)Pn + πPp. Let A ⊂ support(Pu). By regrouping PAn to Pp, Pu can be written as a mixture, i.e., Pu = (1− π′)Pn′ + π′Pp′ , where
π′ = π + (1− π)Pn(A), (7)
Pn′ = PA
c
n
Pn(Ac) , Pp′ = (1− π)PAn + πPp (1− π)Pn(A) + π , (8)
and Pn′ and Pp′ satisfy the anchor set assumption.
When class-conditional distributions Pn and Pp do not satisfy the irreducibility assumption, π cannot be obtained by using CPE methods based on MPE, which will lead to an estimation bias discussed before. However, Theorem 1 shows that the new proportion π′ is always identifiable as Pn′ and Pp′ always satisfy the anchor set assumption. Thus, after regrouping, π′ is identifiable and can be estimated by the existing CPE methods.
Bias reduction According to Theorem 1, to make π′ closer to π, we expect to find the set A looks most dissimilar to the negative class, i.e., Pn(A) is small.
Theorem 2. Let Pp′ and Pn′ be obtained by regrouping a set A∗ := argminA∈S Pn(A) Pp(A) 1 from Pp and Pn. 1). If Pn and Pp satisfy the irreducibility assumption, then π′ = π; 2). if Pn and Pp dissatisfy the irreducibility assumption, then π < π′ < π + (1− π)β∗ = κ∗.
Theorem 2 shows how to properly select a set used for regrouping to make π′ a good approximation of π. Specifically, once A∗ is selected for regrouping, if Pn and Pp satisfy the irreducibility assumption, the new estimation π′ will be identical to π; if Pn and Pp dissatisfy the irreducibility assumption, π′ obtained by employing the distributions Pu and Pp′ will contain a smaller estimation bias compared to κ∗ obtained by employing the distributions Pu and Pp.
Convergence analysis For completeness, we illustrate the convergence property of ReCPE, which is presented by employing the estimator proposed by Blanchard et al. (2010). Let Su, Sp and Sp′ be the samples i.i.d. drawn from Pu, Pp and Pp′ , respectively. Let A be the set used for regrouping. Let h : X → R, h ∈ H, be a function that predicts 1 for all elements in the set A and 0 otherwise, whereH denotes a hypothesis space. Let |S| denote the cardinality of a set S. Let 1{h(x)=1} be an indicator function which returns 1 if h(x) predicts 1 and 0 otherwise. Then Pu(A) can be expressed as ∫ x∈X pp(x)1{h(x)=1}dx, where pp is the density function of the distribution Pu. Let P̂u(A) be
the empirical version of Pu(A), i.e., P̂u(A) = 1|Su| ∑ x∈X 1{h(x)=1}. Similarly, let P̂p′(A) be the empirical version of Pp′(A). Let the error δ,H(Su) denote the difference between Pu(A) and P̂u(A) obtained by exploiting the empirical Rademacher complexity (Mohri et al., 2018). Similarly, let δ,H(Sp′) denote the difference between Pp′(A) and P̂p′(A). We have the following theorem. Theorem 3. Let Pu = (1− π)Pn + πPp. By selecting a set A and regrouping PAn to Pp. Then, with probability 1− 2δ, the estimated class-prior π̂′ based on solving infS∈S,P̂p′ (S)>0 P̂u(S) P̂p′ (S) satisfies
|π̂′ − π| ≤ δ,H(Sp ′)
P̂p′(A) + δ,H(Sp′) +
δ,H(Su)
P̂p′(A) + δ,H(Sp′) + (1− π)Pn(A), (9)
1We have defined that the fraction tends to infinite if its numerator is larger than 0 and its denominator is 0. Additionally, the infimum may not always exist, if it does not exist, we could use a sequence of sets that converges to the infimum value, but the convergence rate can be arbitrarily slow (Scott, 2015).
where δ,H(S) , 2R̂S(H) + 3 √ log 4δ 2|S| , and R̂S(H) is the empirical Rademacher complexity ofH.
To make δ,H(S) converge to 0 with the increasing of the sample size of S, a universal approximation assumption has been proposed by Scott (2015) to ensure that the hypothesis space is large enough to represent a wide variety of interesting functions. Under the assumption, Scott (2015) proved that, with increasing of the size of samples Su and Sp′ , the error between Pu(A) and P̂u(A) will converge
to 0 at a rate O (√
log |Su| |Su|
) , similarly to Pp′(A) and P̂p′(A). Since the empirical Rademacher
complexity R̂X(H) of a hypothesis space H can be upper-bounded by its VC-dimension (Mohri et al., 2018), the both errors based on the empirical Rademacher complexity will also converge to zero with increasing of the sample size. Consequently, the estimation π̂′ = P̂u(A)
P̂p′ (A) will converge to
π′ = Pu(A)Pp′ (A) = π + (1− π)Pn(A) at a rate O
(√ log(min(|Su|,|Sp′ |))
min(|Su|,|Sp′ |)
) .
Computationally efficient identification ofA∗ The following theorem presents how to identifyA∗ with Pu and Pp. Let us define another auxiliary distribution q(X,C), whereC ∈ {0, 1} is the positivevs-unlabeled label i.e., a class label distinguishing between the positive component and the whole mixture. Specifically, priors are q(C = 1) := π1−π and q(C = 0) := 1 1−π ; conditional densities are q(X|C = 1) := Pp and q(X|C = 0) := Pu; class-posterior probabilities are q(C = 0|X) and q(C = 1|X). We have the following theorem. Theorem 4. Let pu and pp be density functions of Pu and Pp, respectively. Let q = P (C = 0)pu + P (C = 1)pp. Let 1A : X → {0, 1} be the identity function which outputs 1 if x ∈ X is in the set A, and 0 otherwise. Then the set A∗ = argminA∈S Ex∼q(X)[1A(X=x)q(C=0|X=x)] Ex∼q(X)[1A(X=x)q(C=1|X=x)] .
For the above optimization, its objective function has two expectations over q, which can have the “exact” empirical solution obtained by replacing expectations with empirical averages: A∗ = argminA⊂S ∑ x∈A q(C=0|X=x)∑ x∈A q(C=1|X=x) .
Approximation of Pp′ with a surrogate As we do not have examples drawn from Pn, it is hard to create Pp′ , let alone sample from it. We approximate Pp′ by using Pp̃′ = PAu +Pp Pu(A)+1
. The following proposition shows that when Pu(A) is small, Pp̃′ is almost identical to Pp′ .
Proposition 2. Let Pp̃′ = PAu +Pp Pu(A)+1 and Pu(A) < . ∀ > 0 and S ∈ S, |Pp′(S)−Pp̃′(S)| ≤ O( ).
Since the gap has the same order as Pu(A) uniformly over S, it is guaranteed that whenever Pu(A) is small, the gap is also small. Practically, we can control the parameter in the above proposition to be small. Specifically, using a small value of the hyper-parameter p in Algorithm 1 will lead to the set A in Theorem 1 to be small, as well as Pu(A). As a consequence, the practical implementation of regrouping is a good approximation of the theory of regrouping as we expected. By now, we have analyzed all of the properties of regrouping and theoretically justified all of the points in its design.

heading: 4 EXPERIMENTS
text: We run experiments on 2 synthetic datasets and 9 real word datasets2. The objectives of employing synthetic datasets are to validate whether the proposed regrouping CPE method reduces the estimation error of the consistent distributional-assumption-free CPE method on the dataset satisfying the irreducibility assumption and does not influence the prediction of the CPE method on the dataset dissatisfying the irreducibility assumption. The hyper-parameter p is also selected from the synthetic datasets. The real-world datasets are used to illustrate the effectiveness of our methods. Although we have introduced a hyper-parameter p and used approximations in the implementation, empirical results on all synthetic and real-world datasets consistently show the superiority of ReCPE.
To have a rigorous performance evaluation, for each dataset, 6× 3× 10 experiments are conducted via random sampling. Specifically, we select {0.25, 0.5, 0.75} fraction of positive examples to be the
2The real word datasets are downloaded from the UCL machine learning database. Multi-class datasets are used as binary datasets by either grouping or ignoring classes.
sample of the positive distribution Pp. We let the rest of the examples be the sample of the unlabeled distribution Pu. In such a way, 3 pairs of empirical positive and unlabeled distributions are generated. Then, we create other 3 pairs of distributions by flipping the labels of all instances in the original datasets. For each pair of distributions, we randomly draw positive and unlabeled samples with sizes of 800, 1600, and 3200, respectively, which are used as input data. Note that, the positive and unlabeled samples have the same size as did in Ramaswamy et al. (2016). For each sample size, 10 repeated experiments are carried out with random sampling. For all experiments, we employ a neural network 3 with 2 hidden layers. Each hidden layer contains 50 hidden units. The batch normalization (Ioffe & Szegedy, 2015) is also employed. The stochastic gradient descent optimizer is used with the batch size 50. The network is trained for 350 epochs with a learning rate 0.01 and momentum 0. The weight decay is set to 1e− 5. The model with the best validation accuracy is used to estimate the positive class-posterior probability P (Y = 1|X = x). We sample the validation set with 20% of the training data size.
4.1 EXPERIMENTS ON SYNTHETIC DATASETS
We create two datasets with one satisfying the irreducibility assumption while the other not. The dataset satisfying the irreducibility assumption is created by sampling from 2 different 10-dimensional Gaussian distributions as the component distributions. One of the distributions has zero means and a unit covariance matrix. Another one has unit means and unit covariance matrix. The dataset dissatisfying the irreducibility assumption is also created by drawing examples from 2 different 10-dimensional Gaussian distributions. One of the distributions has zero means and unit covariance matrix. Another one has unit means and covariance matrix. Then we remove all the data points with P (Y = 1|X) ≥ 0.98 or P (Y = 1|X) ≤ 0.02. For simplicity, in Figure 2, we name two datasets irreducible data and reducible data, respectively.
To validate the correctness of our method and to select a suitable value of the hyper-parameter p, we carry out two experiments. The consistent CPE method KM2 is used as the baseline, which is compared to our method ReKM2, i.e., regrouping version of the KM2. Firstly, we compare the magnitude differences between π̂ and π̂′ (i.e., π̂ − π̂′) with the different fractions of points to be copied from the mixture sample to the component sample, which is illustrated in Figure 2(a). Then we compare differences of the absolute error (i.e., |π̂ − π| − |π̂′ − π|) between the baseline and our method with the increasing of the copy fractions. Note that each point in Figure 2 is obtained by averaging over 6× 3× 10 experiments.
Figure 2(a) validates the correctness of our Theorem 2 and Eq. (7). Theorem 2 states that, by properly selecting the set A, on the dataset dissatisfying the irreducibility assumption (reducible data), π′ should be smaller than the maximum proportion κ∗; on the dataset satisfying the irreducibility assumption (irreducible data), π′ should be close to π. Figure 2(a) perfectly matches this statement. It shows that, on the reducible data,
the values of π̂′ are continuously smaller than π̂ with the copy fraction ≤ 22.5%; on the irreducible data, π̂′ and π̂ have the similar values until the copy fraction ≥ 17.5%. According to Eq. (7), the positive bias of our estimator should become larger with the increase of Pn(A). This fact is reflected by the differences of π̂ − π̂′ become smaller on both datasets when the copy fraction > 15%. Figure 2(b) illustrates the average differences of absolute error between the baseline and the proposed method. On the reducible data, our method continuously outperforms the baseline with the copy
3We employ the neural network because it has a high approximation capability (Csáji et al., 2001).
fraction ≤ 22.5%. However, the differences of average absolute error start to decrease with the copy fraction > 15%. On the irreducible data, the differences of average absolute error are close to zero until the copy fraction > 15%.
By observing Figure 2, we found the prediction of the KM2 estimator will not change much if the copy fraction p is too small. For example, the difference between the estimated mixture proportion by employing samples Su and XP and the ones by employing samples Su and X ′P can be hardly observed if XP and X ′P only differ from in one or two points. For simplicity and consistency, we select hyper-parameter p to be 10% for all the following experiments.

heading: 4.2 EXPERIMENTS ON REAL-WORLD DATASETS
text: We illustrate the absolute estimation errors of different estimators on the real-world datasets. Totally, 7 baseline methods are used in the experiments, which are AlphaMax (AM) (Jain et al., 2016), DEDPUL (DPL) (Ivanov, 2019), Elkan-Noto (EN) (Elkan & Noto, 2008), KM1, KM2 (Ramaswamy et al., 2016), ROC (Scott, 2015), and Rankpruning (RPG) (Northcutt et al., 2017). By using our method, the regrouped version of them are implemented, which are called ReAM, ReDPL, ReEN, ReKM1, ReKM2, ReROC, and ReRPG. In Table 1, we compare the absolute estimation errors of each baseline with those of its regrouped version on different datasets with different sample lengths. Each number in Table 1 is the average over 6× 10 experiments. Table 1 reflects the effectiveness of our regrouping CPE method. Overall, by using our method, the estimation accuracy is increased for most of the popular CPE methods among most of the datasets with different sample lengths. By observing the last row, the regrouped version of the estimators has much smaller average estimation errors except DPL, KM2, and RPG. On the real-world datasets, Regrouping AlphaMax (ReAM) has the smallest average estimation error among all methods.

heading: 5 CONCLUSION
text: In this paper, we investigate how to reduce the estimation bias of the distributional-assumption-free CPE method without irreducibility assumption for PU learning. We have proposed regrouping CPE which can be employed on top of most existing CPE methods. We have also theoretically analyzed the estimation bias of ReCPE. Empirically, it improves all popular CPE methods on various datasets. One future work will focus on how to generate a sample from Pp′ instead of using an approximation.
REPRODUCIBILITY STATEMENT
For theoretical results, we have clearly explained any assumptions. A complete proof of the claims can be founded in the appendix. We have also included an anonymous source code in our supplementary material. For any datasets used in the experiments, a complete description of the data processing steps is provided In Section 4.

heading: ACKNOWLEDGMENTS
text: TL was partially supported by Australian Research Council Projects DP180103424, DE-190101473, IC-190100031, and DP-220102121. BH was supported by the RGC Early Career Scheme No. 22200720 and NSFC Young Scientists Fund No. 62006202. MG is supported by ARC DE210101624. GN and MS were supported by JST AIP Acceleration Research Grant Number JPMJCR20U3, Japan. MS was also supported by the Institute for AI and Beyond, UTokyo.

Review summaries:
This paper studies a relatively little-concerned problem, that is, the problem of class-prior estimation(CPE) in PU scenes. The authors concluded that the existing CPE methods are based on a critical assumption that the support of the positive data distribution cannot be contained in the support of the negative data distribution. However, in actual scenarios, this assumption may not be satisfied. It is also difficult to prove that a certain data set satisfies this assumption. Existing CPE methods will systematically overestimate the class prior when the data does not meet the critical assumption. To remove the assumption to make CPE always valid, a strategy called Regrouping CPE (ReCPE), which builds an auxiliary probability distribution, are proposed so that the support of the positive data distribution is never contained in the support of the negative data distribution. Theoretically, this method can give a more accurate estimate regardless of whether the dataset meets the assumption. The authors also proved the effectiveness of the method through a series of experiments.

This paper studies positive and unlabeled (PU) learning, which apparently is an important problem in machine learning. In many existing researches, the PU classifiers assumes that the irreducibility assumption holds on input data, which, though, may not always be true in many real-world applications. As a result, the learn classifier might not work well due to estimation bias on data prior. To address this problem, this paper proposes to construct a transformed the probability distributions of input data by a re-grouping operation, such as the positive prior cannot be a component (or called as a support) of the negative prior. Good experiment results have been obtained to support the proposed method.

This paper studies the prior $\pi$ in PU learning. More specifically, it studies the estimation method of the prior $\pi$ in a more general case, i.e., without the irreducibility assumption. When unsatisfied, such an assumption will often lead to the overestimation of $\pi$. However, current class-prior estimation methods are usually based on the irreducibility assumption. The authors propose a new CPE problem based on a new auxiliary distribution that always satisfies the irreducibility requirement. The technique is called regrouping, which transforms the true distributions to  Both theoretical and experimental results are included in the paper, showing the validness of the proposed ReCPE method. 

This paper addresses the problem of class-prior estimation (CPE) in positive-unlabeled (PU) learning. The authors consider that the existing methods usually fail if the data distribution dissatisfies the irreducibility assumption. To address this problem, the authors introduce a method named Regroping CPE (ReCPE) which tries to transform the original data distribution to an auxiliary data distribution, such that the produced distribution always guaranteeing the irreducibility assumption.   A practice implementation is proposed by firstly training a binary classifier and then picking some samples whose outputs are mostly dissimilar to the negative examples as the pseudo positive samples. The proposed methods can be considered as a pre-processing method and used together with any CPE method. The experiments on synthetic data show the intuition of the proposed ReCPE and the results on real-world data show the effectiveness of the proposed method when it is combined with other CPE methods.