Introduction
In many domains, particularly bioinformatics, researchers often encounter the "Positive and Unlabeled" (PU) learning problem. This occurs when a small set of confirmed positive examples is available alongside a large set of unlabeled data, but confirmed negative examples are absent. Proving a negative—for instance, that a specific gene is not involved in a disease—is often experimentally prohibitive. Standard supervised learning techniques struggle here as they require well-defined boundaries between two classes. Pierre Geurts' paper, presented at AISTATS 2011, proposes a novel framework that reframes PU learning as an optimization of statistical significance.
Methodology: Learning as a Statistical Hypothesis Test
The core innovation of this work is treating the learning process as a statistical hypothesis test. Instead of minimizing a traditional loss function, the objective is to find a scoring function $f$ that makes the known positive set $S_+$ appear as "surprising" as possible relative to the background distribution.
The Objective and p-value Optimization
The method seeks to minimize the p-value: the probability that a random subset of the data would achieve a score as high as the positive set. To prevent overfitting—where a complex function might make any random subset appear significant—the author introduces an adjusted p-value that accounts for the complexity of the function space being searched.
Reduction to One-Class SVM
For linear score functions, the paper proves a significant theoretical link: minimizing the p-value is equivalent to applying a one-class SVM to a specially constructed "surrogate dataset." This surrogate dataset is formed by taking random subsets of the universe, calculating their average feature vectors, and shifting them by the average feature vector of the known positives. By maximizing the margin to separate these shifted vectors from the origin, the algorithm identifies the direction in feature space where positives are most significantly enriched compared to the background.
Experimental Evaluation
The proposed PU method was evaluated on two gene regulatory network datasets:
- Yeast (S. cerevisiae): 6,178 genes and 80 transcription factors (TFs).
- E. coli: 2,925 genes and 63 TFs, with specific accounting for operons to avoid trivial correlation biases.
The PU method was compared against several baselines, including standard one-class SVMs (1SVM), two-class SVMs treating unlabeled data as negative (2SVM), and center-of-mass (CORR) approaches.
Key Results
As shown in the performance summary, the PU method demonstrated strong results across both organisms. In the Yeast dataset, it achieved the highest average Area Under the ROC Curve (AUC) of 0.880, outperforming both 1SVM and 2SVM. In the E. coli dataset, it remained highly competitive with an AUC of 0.850, significantly outperforming the standard 1SVM (0.791).
Pairwise analysis further validates the robustness of the PU approach. It outperformed the standard 1SVM in approximately 70% to 80% of the individual transcription factor prediction tasks across both organisms. This suggests that treating positives as "outliers" relative to a random background is a more effective prior than the traditional one-class assumption when the positive class is rare.
Conclusion and Future Work
This framework bridges the gap between machine learning and biological enrichment analysis, providing a statistical justification for margin-based classifiers in PU settings. While the current work focuses on linear functions and transductive learning, future directions include extending the method to non-linear kernels and exploring the deeper theoretical links between multiple testing and regularization.
Summary updated