Introduction
Positive-Unlabeled (PU) learning is a critical machine learning paradigm where training data consists of a small set of labeled positive examples and a larger pool of unlabeled data containing both positive and negative instances. A fundamental task in PU learning is the estimation of the class prior ($\alpha$), which represents the true proportion of positive examples hidden within the unlabeled set. Most existing PU algorithms operate under the "Selected At Random" (SAR) assumption, which posits that labeled positives are an unbiased, representative sample of the overall positive distribution. However, in many real-world applications—ranging from biological protein crystallization to financial fraud detection—this assumption is frequently violated due to inherent selection biases in data collection.
Problem Formulation
When the SAR assumption fails, the observed labeled positives follow a biased distribution $f'_1$ rather than the true distribution $f_1$. This discrepancy leads to significant errors in class prior estimation when using standard algorithms, as they mistake the biased sample for a representative one. The core challenge addressed in this work is whether the true class prior $\alpha$ can be recovered even when the labeled positives are heavily biased.
Proposed Methodology: Corrected AlphaMax
The authors introduce a clustering-based "divide and conquer" framework to mitigate the impact of selection bias. The approach is built upon three theoretical foundations:
- Mixing Bias Assumption: This models the biased labeled set as a mixture of different "components" or sub-groups of the positive class. While the overall set is biased, it is assumed that these components can be isolated and treated as locally representative.
- Identifiability Theory: The authors provide mathematical proof that under certain conditions—specifically "disjoint kernel support," where different sub-groups of positives do not significantly overlap in the feature space—the true class prior is uniquely identifiable despite the bias.
- The Algorithm: The practical implementation follows a four-step process. First, $k$-means clustering is applied to the biased labeled positives to identify natural sub-groups. Second, the unlabeled data is partitioned by assigning each point to the nearest cluster center. Third, each partition is treated as an independent, locally unbiased PU problem where standard estimation tools like AlphaMax or Elkan-Noto can be applied. Finally, these local estimates are aggregated using a weighted sum to recover the global class prior $\alpha^*$.
Experimental Evaluation
The method was evaluated on 12 real-world datasets from the UCI Machine Learning Repository, covering diverse domains such as physical chemistry (Gas, Wine), finance (Bank, Housing), and biology (Mushroom, Spambase). To rigorously test the theory, synthetic bias was introduced by non-uniformly sampling clusters of positive examples, simulating the hurdles found in real-world data collection.
Results and Discussion
The "Corrected" algorithm demonstrated superior performance over the "Uncorrected" baseline on biased datasets. Across the 12 datasets, the Mean Absolute Error (MAE) for the class prior estimate dropped significantly from 0.2277 to 0.1579. The authors also evaluated a "Corrected*" variant using ground-truth cluster assignments, which achieved an MAE of 0.0900. This performance gap highlights that the primary bottleneck for the method is the quality of the initial clustering step.
Furthermore, the method proved robust to "over-correction." When applied to datasets that were not biased, the performance remained comparable to standard methods. This suggests that the proposed correction is safe to use even when the presence of bias is uncertain, as it does not introduce significant noise into unbiased estimation.
Conclusion
This research provides a robust framework for class prior estimation in the presence of selection bias. By decomposing a biased global problem into locally unbiased subproblems, the proposed method leverages existing PU learning tools to achieve more accurate estimates. Future work will focus on extending this approach to full distribution recovery, which would allow for the construction of more accurate final classifiers in biased environments.
Summary updated