Positive-unlabeled learning, often abbreviated as PU learning, is a subfield of Machine learning that addresses the problem of binary classification when only positive examples and unlabeled data are available. Unlike standard supervised learning, which requires both positive and negative labeled instances, PU learning operates under the constraint that negative examples are either absent or not explicitly identified. This setting arises in many real-world applications where obtaining reliable negative labels is difficult, expensive, or impractical. The goal is to build a classifier that can distinguish between positive and negative instances, despite the lack of explicit negative training data.
The formal problem was first articulated in the early 2000s, with foundational work by Bing Liu and colleagues at the University of Illinois at Chicago. Their 2002 paper introduced the concept of learning from positive and unlabeled examples, proposing algorithms that treat unlabeled data as a mixture of positive and negative instances. Since then, PU learning has become an important tool in domains such as information retrieval, bioinformatics, and fraud detection, where negative labels are often ambiguous or incomplete.
Problem Formulation
In a standard binary classification task, a training set consists of labeled pairs (x, y) where y ∈ {+1, -1}. In PU learning, the training set is divided into two subsets: a set of positive examples P, where all instances are known to be positive, and a set of unlabeled examples U, which may contain both positive and negative instances. The key challenge is that the unlabeled set is a mixture, and the proportion of positive instances in U is unknown. This makes the learning problem fundamentally different from standard supervised learning, as the absence of negative labels introduces a bias that must be corrected.
A common assumption in PU learning is that the labeled positive set is a random sample from the true positive distribution, often referred to as the "selected completely at random" (SCAR) assumption. Under this assumption, the probability of a positive instance being labeled is constant and independent of its features. This allows for the development of unbiased estimators of the classification risk, which can be optimized using techniques from statistical learning theory.
Approaches and Algorithms
Several families of algorithms have been developed to tackle PU learning. One early approach is the two-step strategy, which first identifies reliable negative examples from the unlabeled set using a heuristic, and then trains a standard classifier on the positive and reliable negative examples. This method, popularized by Liu and his collaborators, often uses a spy technique or a distance-based criterion to select likely negatives. However, these methods can be sensitive to the quality of the initial negative selection.
A more principled approach is based on biased learning, where the unlabeled data is treated as noisy negative examples. The classifier is trained to minimize a weighted loss function that accounts for the fact that some unlabeled instances are actually positive. This can be formulated as a cost-sensitive learning problem, where the cost of misclassifying a positive instance in the unlabeled set is adjusted based on the estimated prior probability of positives.
In recent years, Deep learning methods have been applied to PU learning, particularly using neural networks. One notable development is the unbiased risk estimator proposed by du Plessis, Niu, and Sugiyama in 2014, which provides a theoretically grounded way to train classifiers without negative labels. This estimator has been extended to handle non-convex losses and has been shown to be effective in high-dimensional settings, such as image classification and text classification.
Applications
PU learning has found widespread use in domains where negative labels are scarce or unreliable. In information retrieval, it is used for document classification and spam filtering, where only a small set of relevant documents is known, and the rest are unlabeled. In bioinformatics, PU learning is applied to predict protein-protein interactions and gene functions, where experimentally confirmed positive interactions are available, but negative interactions are rarely verified.
Another significant application is in fraud detection and anomaly detection. For example, in credit card fraud detection, transactions labeled as fraudulent are rare and often incomplete, while the vast majority of transactions are unlabeled. PU learning allows models to be trained on confirmed fraud cases and the large pool of unlabeled transactions, improving detection rates without requiring exhaustive labeling. Similarly, in medical diagnosis, PU learning can be used to identify patients with a rare disease based on a small set of confirmed cases and a large set of unlabeled patient records.
Challenges and Extensions
Despite its utility, PU learning faces several challenges. The primary difficulty is the estimation of the class prior, i.e., the proportion of positive instances in the unlabeled set. Incorrect estimation can lead to biased classifiers and poor performance. Researchers have proposed various methods for prior estimation, including using cross-validation and moment-matching techniques, but the problem remains open in many practical settings.
Another challenge is the presence of label noise in the positive set. In some applications, the labeled positive examples may themselves be mislabeled, which can degrade the performance of PU learning algorithms. Robust variants have been developed to handle such noise, often by incorporating additional assumptions about the noise process.
Extensions of PU learning include semi-supervised PU learning, where a small number of negative labels are also available, and PU learning with multiple positive sets, where different sources of positive examples may have different distributions. These extensions aim to relax the strict assumptions of the basic PU setting and improve applicability to complex real-world problems.
Relationship to Other Learning Paradigms
PU learning is closely related to other weakly supervised learning paradigms, such as semi-supervised learning and learning with noisy labels. In semi-supervised learning, both labeled positive and negative examples are available, along with unlabeled data, whereas PU learning lacks negative labels entirely. In learning with noisy labels, the training set contains both positive and negative labels, but some labels are incorrect. PU learning can be viewed as an extreme case of noisy labels, where all negative labels are missing, and some unlabeled instances are actually positive.
The connection to one-class classification is also notable. One-class classification aims to model the positive class distribution and identify outliers, which is similar to PU learning when the unlabeled set is assumed to contain mostly negatives. However, PU learning explicitly accounts for the presence of positives in the unlabeled set, making it more general.
Future Directions
As Artificial intelligence continues to advance, PU learning is being integrated into more complex models, including large language models and transformer-based architectures. These models can leverage large amounts of unlabeled text data, and PU learning provides a framework for fine-tuning them with only a small set of positive examples. This is particularly relevant in domains like legal document analysis and scientific literature mining, where positive examples are scarce but unlabeled corpora are vast.
Research is also exploring the use of PU learning in reinforcement learning and online learning settings, where the data distribution may change over time. Additionally, the development of theoretical guarantees for PU learning under various assumptions remains an active area of study, with the goal of providing robust and reliable methods for practitioners.