Abstract
Motivated by applications in protein function prediction, we consider a challenging supervised classification setting in which positive labels are scarce and there are no explicit negative labels. The learning algorithm must thus select which unlabeled examples to use as negative training points, possibly ending up with an unbalanced learning problem. We address these issues by proposing an algorithm that combines active learning (for selecting negative examples) with imbalance-aware learning (for mitigating the label imbalance). In our experiments we observe that these two techniques operate synergistically, outperforming state-of-the-art methods on standard protein function prediction benchmarks.
Introduction
In many real-world classification tasks, such as Automated Protein Function Prediction (AFP), researchers often possess confirmed examples of a class (positive labels) but lack explicit negative annotations. This scenario, known as Positive and Unlabeled (PU) learning, presents two primary challenges. First, the "Noisy Negative Trap": treating all unlabeled data as negative introduces noise from undiscovered positives. Second, the "Imbalance Wall": the extreme scarcity of positive labels often leads to models that ignore the positive class entirely due to the overwhelming majority of negative examples.
Methodology
This paper introduces a two-phase framework that leverages the synergy between active learning and cost-sensitive classification to navigate these hurdles.
Phase 1: Active Negative Selection
Rather than selecting negatives at random, the framework employs an Active Learning (AL) strategy. Starting with a small seed of positives and random negatives, the algorithm iteratively queries the unlabeled pool for the most "informative" instances—those where the current model's confidence is lowest (e.g., points closest to the SVM decision boundary). By focusing on the boundary where hidden positives are most likely to reside, the model develops a sharper separation than methods that seek only "reliable" (distant) negatives.
Phase 2: Imbalance-aware Classification
To address the resulting class imbalance, the final classifier is trained using cost-sensitive techniques. For Support Vector Machines (SVM), higher penalties are assigned to misclassifying positives ($C_+$) relative to negatives ($C_-$). For Random Forests (RF), balanced bootstrap sampling is utilized. This ensures that the rare positive labels remain the primary drivers of the model's decision logic.
Experimental Results
The framework was evaluated on biological benchmarks for Saccharomyces cerevisiae and Homo sapiens using protein-protein interaction networks from the STRING database. Performance was measured using a temporal holdout to simulate realistic discovery conditions.
As shown in the figure above, the SVM implementation (SVM AL) consistently outperformed the Random Forest variant in both predictive power and efficiency. Specifically, SVM AL demonstrated a higher F-measure across various negative sample budgets (s) while requiring significantly less computational time. The Area Under the Precision-Recall curve (AUPR) for SVM AL was significantly superior to state-of-the-art baselines like GBA and COSNet ($p$-value < 0.001).
Discussion and Conclusion
A key insight of this work is that active learning and imbalance-aware techniques are mutually dependent in the PU setting; neither provides significant gains in isolation. While the SVM variant scales efficiently for genome-wide predictions, the Random Forest implementation struggles with computational overhead as the negative budget increases. Future work may involve incorporating the hierarchical structure of the Gene Ontology to further refine prediction accuracy, though the current "flat" approach offers high versatility for domains lacking such structured metadata.
Summary updated