Abstract
Estimating the class prior—the proportion of positive examples in an unlabeled dataset—is a fundamental challenge in Positive-Unlabeled (PU) learning. Traditional methods often suffer from high computational complexity or poor performance in high-dimensional spaces. This paper introduces DistCurve, a fast, nonparametric algorithm that leverages the geometric properties of nearest-neighbor distances. By constructing a "distance curve" and identifying its characteristic "elbow point" using a neural network trained on synthetic data, DistCurve achieves state-of-the-art accuracy. Furthermore, it demonstrates superior scalability, processing large datasets orders of magnitude faster than kernel-based competitors.
Introduction
In Positive-Unlabeled (PU) learning, the objective is to learn from a set of confirmed positive examples and a larger unlabeled set containing both positive and negative instances. A prerequisite for many downstream tasks, such as recovering posterior probabilities or standard performance metrics, is knowing the class prior ($\alpha$). However, estimating $\alpha$ accurately and efficiently remains difficult, especially as dataset sizes and dimensionalities grow. Existing methods often rely on $O(N^2)$ kernel operations, making them impractical for modern large-scale applications.
The DistCurve Method
The proposed DistCurve algorithm operates on a simple yet powerful geometric intuition. It consists of two primary stages: curve construction and prior estimation.
- Constructing the Distance Curve: The algorithm iteratively samples a known positive instance, finds its nearest neighbor in the unlabeled mixture, records the distance, and removes that neighbor. Initially, the algorithm tends to pick "true" positives hidden within the unlabeled set, resulting in small, stable distances. Once the positive component is exhausted, the algorithm is forced to select negative examples, causing a sharp increase in distance.
- Estimation via Neural Network: To robustly identify this "elbow point" ($\alpha^*$), the authors employ a multi-layer perceptron (MLP). The MLP is trained on one million synthetic datasets generated from various Beta distributions, allowing it to learn a wide variety of curve shapes and generalize to real-world data.
For high-dimensional data, such as text, DistCurve utilizes a univariate transform. A "nontraditional" classifier is trained to separate labeled positives from the unlabeled set, and its scores are used as a one-dimensional feature space for distance calculations.
Experimental Evaluation
The algorithm was rigorously tested on 40 datasets, including 30 multi-dimensional real-valued sets from the UCI repository and 10 high-dimensional text mining datasets.
Key Results
DistCurve demonstrated exceptional performance in both accuracy and speed:
- Accuracy: It achieved a Mean Rank Error (MRE) of 1.7, outperforming established benchmarks like AlphaMax (2.8) and Elkan & Noto (3.1).
- Robustness: The method was particularly effective for text mining, where it consistently ranked as the top performer, likely due to the effectiveness of the SVM-based univariate transform.
- Scalability: DistCurve is significantly faster than kernel-based methods. On average, it completed tasks in 66 seconds that took competing methods nearly 47 minutes (2,818 seconds).
Discussion and Conclusion
DistCurve represents a significant advancement in PU learning by combining geometric exhaustion with simulation-based learning. Its ability to "peel away" the positive component of a mixture provides an intuitive and efficient path to class prior estimation. While the method's performance in high dimensions depends on the quality of the initial univariate transform, its empirical success and scalability make it a highly practical tool for large-scale data analysis. Future work will focus on providing formal theoretical guarantees for the convergence of the distance curve spike.
Summary updated