Class Prior Estimation with Biased Positives and Unlabeled Examples

Shantanu Jain, Justin Delano, Himanshu Sharma, Predrag RadivojacAAAI 2020 · DOI

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.

Illustration of the discrepancy between the true positive distribution ($f_1$) and the biased observed distribution ($f'_1$).

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:

  1. 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.
  2. 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.
  3. 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.

Performance comparison on datasets with and without bias. The corrected method significantly reduces MAE in biased scenarios while remaining robust in unbiased ones.

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

BibTeX
@inproceedings{jain2020class,
  author = {Shantanu Jain and Justin Delano and Himanshu Sharma and Predrag Radivojac},
  title = {{Class Prior Estimation with Biased Positives and Unlabeled Examples}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5848},
}
Figure