In standard binary classification, we hand a model a balanced diet of examples: "here is what a cat looks like (positive), and here is what a cat does not look like (negative)." The model draws a boundary between the two clusters.
But real-world data rarely arrives so neatly packaged. Consider diagnosing a rare disease using health records, as explored in RareBERT: Transformer Architecture for Rare Disease Patient Identification using Administrative Claims. You have a small group of patients confirmed to have the disease (positives). The rest of the population is a massive pool of undiagnosed individuals (unlabeled). Some of these unlabeled individuals are truly healthy (negatives), but others are simply undiagnosed or unrecorded cases (hidden positives).
This scenario is the core of Positive-Unlabeled (PU) learning. We possess a set of confirmed positive examples and a vast sea of unlabeled data containing an unknown mixture of both positives and negatives.
The Naive Trap
The most intuitive workaround is to treat all unlabeled data as negative. If you train a standard classifier this way, you are telling the model that the hidden positives in the unlabeled pool are definitive examples of the negative class.
This introduces a severe, destructive bias. The model is penalized whenever it correctly identifies the features of a hidden positive instance. Instead of drawing a clean boundary between classes, the decision boundary collapses, shrinking away from the positive cluster to avoid the "negatives" that actually belong to the positive class. As noted by Wright et al. in Claim Check-Worthiness Detection as Positive Unlabelled Learning, treating incomplete annotations as true negatives severely degrades a model's ability to discover hidden patterns.
To solve this without explicit negative labels, we have to exploit the statistical relationship between the labeled positive data and the unlabeled mixture.
The SCAR Assumption and the Proportionality Shortcut
In a seminal paper, Learning classifiers from only positive and unlabeled data, Charles Elkan and Keith Noto introduced a powerful mathematical insight that underpins much of modern PU learning. They formalized the Selected Completely at Random (SCAR) assumption.
Under SCAR, we assume that the labeled positive examples are a uniform random sample of all true positive examples in the dataset. In other words, whether a positive instance gets a label depends entirely on chance, not on its specific features.
Let $y \in \{0,1\}$ be the true binary label (where $1$ is positive and $0$ is negative), and let $s \in \{0,1\}$ indicate whether an instance is labeled ($s=1$ means it is in our labeled positive set). By definition, only true positives can be labeled, so if $s=1$, then $y=1$.
The SCAR assumption states that the probability of a positive instance being labeled is a constant, independent of its features $x$:
$$P(s=1 \mid y=1, x) = P(s=1 \mid y=1) = c$$
Here, $c$ is the class prior—the fraction of positive instances that actually received a label.
Now, let's look at what happens when we train a standard, off-the-shelf classifier to distinguish between our labeled data ($s=1$) and our unlabeled data ($s=0$). This model estimates $P(s=1 \mid x)$. Using the law of total probability and our SCAR assumption, we can expand this:
$$P(s=1 \mid x) = P(s=1, y=1 \mid x) = P(s=1 \mid y=1, x) \cdot P(y=1 \mid x)$$
Substituting $c$ into the equation yields:
$$P(s=1 \mid x) = c \cdot P(y=1 \mid x)$$
This is the foundational epiphany of PU learning: The probability that an item is labeled given its features is directly proportional to the true probability that it is positive.
This means that if you train a standard classifier to separate the labeled data from the unlabeled data, the model will learn the correct decision boundary. The shape of the boundary is accurate because $P(s=1 \mid x)$ tracks $P(y=1 \mid x)$ perfectly; the probabilities are simply scaled down by the constant factor $c$. To get the true probability $P(y=1 \mid x)$, you just need to divide the model's output by $c$.
Two Paths to Practical Classification
While the Elkan and Noto framework provides a elegant theoretical foundation, researchers have developed two primary paradigms to train robust models in practice: Two-Step Methods and Unbiased Risk Estimation.
1. Two-Step Methods: Finding "Reliable Negatives"
If the primary issue is that the unlabeled pool is contaminated with hidden positives, why not try to clean it? Two-step methods aim to isolate a pristine subset of the unlabeled data that is almost certainly negative, and then run standard supervised learning.
A classic implementation of this is the "Spy" technique, utilized by Li et al. in Distributional Similarity vs. PU Learning for Entity Set Expansion. The intuition is straightforward:
- Send in the Spies: Randomly sample a small percentage (e.g., 10%) of your known positive examples, strip away their labels, and hide them inside the unlabeled pool. These are your "spies."
- Train a Preliminary Model: Train a classifier treating the remaining labeled data as positive and the entire unlabeled pool (now containing the spies) as negative.
- Evaluate and Threshold: Because the spies are truly positive, the model should assign them relatively high positive probabilities. Look at the distribution of probabilities assigned to these hidden spies. Find the lowest probability score among them.
- Identify Reliable Negatives: Any original unlabeled instance that scored lower than your spies can be safely assumed to be a "reliable negative." You can now train a final binary classifier using your known positives and these newly minted reliable negatives.
2. Unbiased Risk Estimation: Correcting the Loss Function
Instead of altering the data, algebraic approaches alter the objective function itself. In standard machine learning, we minimize a loss function (or risk) over both positive and negative samples. In a PU setting, we lack the negative samples to compute the negative component of the loss.
However, because the unlabeled distribution is a weighted combination of the positive and negative distributions, we can express the missing negative loss mathematically. As demonstrated by du Plessis et al. in Analysis of Learning from Positive and Unlabeled Data, the expected loss on the negative class can be calculated by taking the loss over the entire unlabeled dataset and subtracting the portion that belongs to the hidden positives.
Mathematically, the risk estimator is rewritten so that the model computes loss on the positive data, loss on the unlabeled data, and then subtracts a weighted version of the positive loss to cancel out the bias of hidden positives. This allows gradient descent to optimize the true, unbiased classification risk directly, without ever needing to label a single negative instance.
The Missing Piece: Estimating the Class Prior
Both paradigms rely on a critical piece of information: the class prior ($c$ or $\pi_p$), which tells us exactly what fraction of the unlabeled data (or total data) is positive. If you underestimate how many positives are hidden in the unlabeled pool, your model will still suffer from false-negative bias. If you overestimate it, the model will overcorrect.
To solve this, researchers developed algorithms like TIcE (Estimating the Class Prior in Positive and Unlabeled Data Through Decision Tree Induction). TIcE uses decision trees to isolate regions of the feature space where the density of labeled positive examples is maximized. By finding regions that are "purely positive," the algorithm can look at the ratio of labeled to unlabeled instances in that neighborhood to deduce the global scaling factor $c$ quickly and efficiently.
Why It Matters
PU learning transforms how we handle domains where confirmation is asymmetric. In distant supervision for text processing—such as the Named Entity Recognition framework proposed by Peng in Distantly Supervised Named Entity Recognition using Positive-Unlabeled Learning—a dictionary can confirm that a word is an entity (positive), but the absence of a word from the dictionary does not mean it isn't an entity (unlabeled).
By shifting our framing from "positive vs. negative" to "positive vs. unknown mixture," PU learning allows machine learning models to navigate incomplete annotations, open-world environments, and noisy datasets without succumbing to systematic bias.