PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning from positive and unlabeled data: a survey

Jessa Bekker, Jesse Davis

arXiv:1811.04820v3cs.LGstat.ML

TL;DR

PU learning addresses binary classification when only positive and unlabeled examples are available, a setting common in applications where missing labels do not imply negative cases. This survey organizes the field around seven research questions, reviews its assumptions, methods, evaluation approaches, and applications, and identifies future directions while noting unresolved practical issues.

  • Problem

    PU learning must distinguish positive and negative examples when training data contains labeled positives and unlabeled examples that may belong to either class.

  • Method

    The survey provides a comprehensive overview organized around seven key research questions covering PU formalization, assumptions, class priors, learning, evaluation, applications, and related areas.

  • Results

    The survey reports that multiple class-prior estimation techniques exist, while kernel embedding KM2 and TIcE were most accurate on SCAR PU data in a small benchmark, with TIcE significantly faster.

  • Takeaways & Limitations

    The survey connects class-prior estimation to PU algorithm design through weighting data or modifying algorithms to use fractional counts, and synthesizes approaches for evaluating PU models.

  • Takeaways & Limitations

    Practical comparison remains limited because much evaluation uses converted fully labeled datasets, while direct quantitative comparisons and real-world PU benchmarks are scarce.

Abstract

from arXiv · show

Learning from positive and unlabeled data or PU learning is the setting where a learner only has access to positive examples and unlabeled data. The assumption is that the unlabeled data can contain both positive and negative examples. This setting has attracted increasing interest within the machine learning literature as this type of data naturally arises in applications such as medical diagnosis and knowledge base completion. This article provides a survey of the current state of the art in PU learning. It proposes seven key research questions that commonly arise in this field and provides a broad overview of how the field has tried to address them.

1 Introduction

PU learning addresses binary classification when training data contains labeled positive examples and unlabeled examples that may be either positive or negative. The survey organizes the field around seven research questions and reviews how researchers address them.

  • PU learning uses positive and unlabeled training examples, with each unlabeled example potentially belonging to either class.
  • PU data naturally arises in personalized advertising and medical records, where unobserved negatives cannot safely be treated as negative examples.
  • The survey frames PU learning through seven questions covering formalization, assumptions, class-prior estimation, learning, evaluation, applications, and connections to machine learning.
  • It provides a comprehensive overview of how the research community addresses these questions and concludes with perspectives on future research directions.

2 Preliminaries on PU Learning

PU learning extends binary classification by observing only some positives and no labeled negatives, with labels generated through a propensity-based mechanism. Its preliminaries distinguish data-collection scenarios and relate the class prior to label frequency.

  • 2.2 PU Learning: PU learning retains the binary-classification goal but labels only some positive examples, while none of the negative examples are labeled.
  • 2.2 PU Learning: A PU example is represented as (x, y, s), where s=1 guarantees a positive class and s=0 leaves the class unknown.
  • 2.3 Labeling Mechanism: The propensity score e(x)=Pr(s=1|y=1,x) gives the probability that a positive example is selected for labeling, making labeled positives a biased version of the positive distribution.
  • 2.4 The Single-Training-Set and Case-Control Scenarios: PU data arises either from one training set containing positives and unlabeled examples or from two independently drawn datasets, called the single-training-set and case-control scenarios.
  • 2.4 The Single-Training-Set and Case-Control Scenarios: The single-training-set scenario assumes an i.i.d. dataset from the real distribution, with a fraction c of positives labeled according to individual propensity scores.
  • 2.5 Relationship Between the Class Prior and the Label Frequency: The class prior α and label frequency c are related quantities whose conversion depends on whether data follow the single-training-set or case-control scenario.

3 Assumptions to Enable PU Learning

PU learning is difficult because an unlabeled example may be either negative or a positive omitted by the labeling mechanism, so methods require assumptions about labeling, class distributions, or both. The survey describes SCAR, SAR, and PGPU mechanisms, alongside distributional assumptions such as negativity and separability, and explains how these assumptions enable learning.

  • Unlabeled examples may be negative or positive examples whose labels were not observed, making PU learning impossible without additional assumptions.Assumptions may concern the labeling mechanism, class distributions, or both; class-prior information is also important for many methods.
  • Selected Completely At Random: SCAR assumes labeled examples are a uniform subset of positive examples, enabling standard binary classifiers through minor data or algorithm modifications.Under SCAR, labeled examples are an i.i.d. sample from the positive distribution, and classifiers predicting Pr(s = 1|x) preserve the ranking of Pr(y = 1|x).
  • Selected Completely At Random: Under SCAR, the propensity score is constant and equals the label frequency c, while positive and unlabeled data remain distinguishable through the labeling indicator.The relation Pr(y = 1|x) = Pr(s = 1|x)/c converts a non-traditional classifier into a traditional classifier when c is known.
  • Selected At Random: SAR allows the probability of labeling a positive example to depend on its attributes, and modeling that mechanism can yield an unbiased classifier.When the labeling mechanism is unknown, additional assumptions are needed; the survey motivates SAR by application-specific labeling bias.
  • Probabilistic Gap: PGPU assumes that examples with smaller probabilistic gaps are less likely to be labeled, with propensity increasing monotonically with the gap.Observed gaps are no larger than real gaps and preserve their ordering, supporting reliable positive or negative-example extraction under stated conditions.
  • Distributional Assumptions: Common distributional assumptions include treating all unlabeled examples as negative and assuming separable classes, although the former is explicitly acknowledged as false in general.Separability means that some classifier can perfectly distinguish the positive and negative classes.

4 PU Measures

PU learning makes standard evaluation and tuning difficult because unlabeled data mixes positive and negative examples. Under assumptions such as SCAR, researchers derive alternative metrics, hypothesis tests, and bounds for traditional metrics.

  • Standard metrics such as accuracy, F1, and mean square error cannot generally be computed directly from positive and unlabeled data.This complicates both model evaluation and hyperparameter tuning.
  • Under SCAR, recall can be estimated from PU data, but precision cannot, so the F1 score itself is not directly identifiable.A related criterion can still be estimated because it is high when both precision and recall are high.
  • 4.2 Hypothesis Testing: The G-test gives the same independence result from supervised and PU data, although its statistical power differs by a constant correction factor.The correction depends on the amount of labeled data and can guide how much additional data is needed for a desired power.
  • 4.3 Computing Standard Evaluation Metrics: Under certain conditions, traditional metrics can be bounded by estimating the class prior and comparing rank distributions of observed and hidden positives.These quantities support contingency tables for accuracy, true-positive rate, false-positive rate, and precision.

5 PU Learning Methods

PU learning methods are organized around two-step techniques, biased learning, and class-prior incorporation. Two-step methods first identify reliable examples and then apply supervised or semi-supervised learning, with many variants differing in how reliability is determined.

  • PU methods fall into three categories: two-step techniques, biased learning, and class-prior incorporation.The two-step approach identifies reliable negatives before training on labeled positives and selected negatives.
  • 5.1 Two-Step Techniques: Two-step methods rely on separability and smoothness, assuming positives resemble labeled positives while negatives differ from them.These assumptions motivate distance- and similarity-based selection procedures.
  • 5.1 Two-Step Techniques: Most papers propose fixed combinations of step-specific methods, although the method used at each step can in principle be chosen freely.Table 4 lists combinations reported in the literature and marks variations with an asterisk.
  • 5.1 Two-Step Techniques: Two-step methods select unlabeled examples that differ sufficiently from positives as reliable negatives, then train a supervised or semi-supervised classifier.The pipeline may optionally add reliable positives and select the best classifier.
  • 5.1 Two-Step Techniques: Proposed reliability procedures include spies, Rocchio, PNLH, graph-based learning, probabilistic gaps, clustering, nearest neighbors, DILCA, and generative models.They differ in features, distances, clustering, probability estimates, and criteria for selecting reliable examples.
  • 5.1 Two-Step Techniques: Other variants select reliable negatives using k-means, distance to positives, clusters without positives, trainable categorical distances, or low positive-generation probability.Some methods instead augment the unlabeled set with likely negatives or generate artificial negatives for specific settings.

5.2 Biased Learning

Biased learning treats unlabeled examples as noisy negatives while using SCAR-based corrections during training or tuning. Its methods include weighted classifiers, SVM variants, robust ensembles, logistic regression, clustering, and matrix completion.

  • Biased PU learning treats unlabeled examples as negative examples with class-label noise and uses SCAR-based corrections to account for that noise.Corrections include asymmetric penalties and PU-suitable tuning criteria.
  • 5.2.1 Classification: Support vector methods dominate biased learning, including biased SVM, iterative biased SVM, WUS-SVM, RankSVM, Biased Twin SVMs, NPSVM, and LUHC.These methods modify penalties, weights, iterations, regularization, or classification thresholds.
  • 5.2.1 Classification: Noisy negative data can cause a genuinely positive example to receive excessive negative importance, making learning harder.Bagging and least-squares SVM variants are used to address this issue.
  • 5.2.1 Classification: Weighted logistic regression assigns larger weights to positive examples using the positive and negative class priors.Topic-Sensitive pLSA instead uses must-link constraints among positives and cannot-link constraints across classes, especially when few positives are labeled.
  • 5.2.2 Matrix Completion: Binary matrix completion frames known ones as positives and zeros as unlabeled, using ShiftMC for probability recovery and BiasMC for complete-matrix recovery.The methods incorporate the class prior through unbiased loss estimation or asymmetric penalties.

5.3 Incorporation of the Class Prior

Class-prior incorporation uses SCAR information, or propensity scores under SAR, to adjust predictions, datasets, losses, and counts. The survey describes postprocessing, preprocessing, method modification, rebalancing, label-probability weighting, and empirical-risk estimators.

  • Under SCAR, class-prior methods use postprocessing, preprocessing, or method modification to incorporate the known or estimated prior.Under SAR, propensity scores can similarly enable learning, though this has only been explored for empirical-risk-minimization preprocessing.
  • The class prior is equivalent to the label frequency c, allowing methods to estimate or tune it using PU evaluation criteria.The label frequency is defined as c = Pr(s = 1)/α.
  • 5.3.1 Postprocessing: A classifier trained to distinguish labeled from unlabeled examples can be converted into class-probability predictions by dividing Pr(s = 1|x) by c.If probabilities are unnecessary, the decision threshold can instead be shifted from τ to τ_PU = cτ.
  • 5.3.2 Preprocessing: Preprocessing creates a weighted dataset that standard fully supervised methods can use, including rebalancing, label-probability incorporation, and empirical-risk-minimization approaches.The goal is for learning on the resulting dataset to match learning from fully labeled data.
  • 5.3.2 Preprocessing: Rebalancing methods adjust example weights so a PU-trained classifier uses the desired target threshold without changing the threshold itself.The resulting special cases include BiasMC and weighted logistic regression.
  • 5.3.2 Preprocessing: Rebalancing is appropriate for classification at a target threshold but not for unbiased estimates of Pr(y = 1|x).This limits its use when calibrated probability estimates are required.
  • 5.3.2 Preprocessing: Label-probability incorporation duplicates unlabeled examples as partially positive and partially negative, while labeled positives receive positive weight 1.The weights are based on estimated probabilities from a non-traditional classifier.
  • 5.3.2 Preprocessing: Empirical-risk methods rewrite the unavailable fully supervised risk using expectations over labeled, unlabeled, general, and positive distributions.In the case-control scenario, the general expectation can be replaced by the unlabeled distribution.

5.4 Relational Approaches

Relational PU learning adapts PU assumptions and estimation methods to knowledge-base completion and relational rule learning. Approaches range from closed-world-style assumptions to methods that explicitly use SCAR, separability, or smoothness.

  • Relational PU learning: Knowledge-base completion is a PU task because known relationships are positive while potential additions remain unlabeled.Many methods nevertheless assume that facts absent from the knowledge base are negative.
  • Class-prior methods: When SCAR holds, relational versions of class-prior incorporation methods can estimate the prior directly from relational PU data.TIcER is presented as a relational version of TIcE for this purpose.
  • Rule learning: Aleph’s PosOnly setting assumes separability and seeks the simplest theory covering all positives while introducing few additional facts.
  • One-class methods: RelOCC uses a tree-based distance method under smoothness but does not use unlabeled examples during training, so it is not truly PU learning.
  • Relational assumptions: AMIE+ uses partial completeness to estimate rule confidence more precisely when at least one object is known for a subject–relationship pair.RC confidence further uses rule-specific SCAR assumptions and expected relation cardinalities.
  • Relational PU methods: PULSE handles relational disjunctive concepts with up to k positive subclasses, assuming SCAR within each subclass without requiring equal label frequencies.

5.5 Other Methods

Other PU methods fall outside the survey’s three main categories and include generative, co-training, streaming, and EM-based approaches. These methods extend PU learning to distribution modeling, multiple views, evolving data, and SAR settings.

  • Generative methods: GAN-based PU methods model the positive and negative distributions.
  • Co-training: Co-training applies two-view learning to PU data by seeking agreement between two models.
  • Data streams: Multiple studies address classification on data streams containing PU data.
  • SAR methods: EM can handle SAR PU data when propensity scores depend only on a known subset of attributes.The EM procedure simultaneously trains the classifier and estimates propensity scores.

5.6 Comparison of PU Learning Methods

Choosing a PU method depends primarily on which assumptions are likely to hold in the application. The survey contrasts methods suited to separability, SCAR, probability estimation, and robustness to assumption violations.

  • Method selection: Separability favors two-step techniques, whereas SCAR favors biased learning or methods that incorporate the class prior.
  • Method selection: PGPU is the only identified method combining a two-step procedure with separability and uses that assumption to find the decision boundary.
  • Probability estimation: ERM data reweighting, ShiftMC, and POS4.5 should be considered when unbiased estimates of Pr(y = 1|x) are desired under SCAR or SAR.ERM data reweighting can require negative weights, which some classifiers and implementations cannot handle.
  • Robustness: Rebalancing and class-prior incorporation are sensitive to SCAR, while ensemble methods provide more robustness and smoothness can relax SCAR.

6 Class Prior Estimation from PU Data

Class-prior estimation is useful because knowing the prior simplifies PU learning under SCAR, but available estimators rely on different assumptions and have practical trade-offs. The survey covers classifier-, density-, tree-, ROC-, and kernel-based approaches, while noting that the best practical method remains unresolved.

  • Motivation: Knowing the class prior significantly simplifies PU learning under SCAR, motivating direct estimation from PU data.
  • Non-traditional classifiers: Non-traditional classifier methods estimate label frequency from predicted labeling probabilities, but the separable-class approach requires well-calibrated probabilities.
  • Partial matching: Partial matching estimates the prior by minimizing divergence between a density estimated from labeled positives and the complete-data density after scaling.
  • Partial matching: Overlapping positive and negative distributions cause partial matching to overestimate the prior; penalized divergences address this by penalizing α Pr(x|y = 1) > Pr(x).
  • Decision tree induction: TIcE searches decision-tree subdomains for the largest lower bound on label frequency and is more robust and faster than a related single-instance method.Its robustness comes from maximizing over sets of instances, and its speed from focusing on branches that can yield stricter bounds.
  • ROC approaches: ROC-based estimation selects the largest prior yielding optimal positive and total-density likelihoods while balancing TPR and FPR within a hypothesis space.
  • Kernel embeddings: Kernel-embedding methods use the positive-function assumption and prove convergence to the true prior under certain assumptions.
  • Comparison: Empirical comparisons favor KM2 and TIcE on SCAR data, with TIcE significantly faster, while KM2 is more accurate than TIcE on SAR data.The survey cautions that the best approach in practice remains an open issue because comparisons often use artificially constructed PU data.

7 Sources of PU Data and Applications

PU data arises when positive information is recorded more readily or when unlabeled examples cannot safely be treated as negative. The survey covers applications ranging from diagnosis and recommendation to biological discovery, sensing, and anomaly detection.

  • Sources of PU Data: PU data occurs when unlabeled examples may include positives, such as undiagnosed patients, non-purchased items, or students without indirect activity labels.Medical records list diagnosed diseases but not necessarily undiagnosed ones; purchases, likes, spam tags, and sport-class registration provide positive examples while others remain unlabeled.
  • Sources of PU Data: Case-control settings use separate datasets: one containing only positives and another sampled from the broader population.The survey illustrates this with upper-class health-center data as positives and randomly selected health-center data as unlabeled.
  • Applications: PU formulations also cover incomplete knowledge bases, identification tasks, one-class classification, and inlier-based outlier detection.Known facts or examples define positives, while candidate facts, genes, or population data supply unlabeled instances.
  • Applications: Further applications span drug interaction discovery, ecological habitat modeling, targeted marketing, and remote sensing.Across these settings, non-observation, unknown interactions, or diverse negative classes leave many examples unlabeled.
  • Applications: Applications include localization, deceptive-review filtering, focused crawling, time-series anomaly detection, disease-gene identification, and protein or gene-network analysis.These tasks exploit positive examples while avoiding costly or unreliable exhaustive negative labeling.

8 Related Fields

PU learning overlaps with semi-supervised learning, one-class classification, label-noise modeling, missing-data mechanisms, and multiple-instance learning. Its distinctions chiefly concern which classes are labeled, how unlabeled data defines the domain, and how labels are generated.

  • Semi-supervised learning: Semi-supervised learning assumes labeled examples from all classes and can extend beyond binary classification, whereas PU learning has positive and unlabeled data.Some semi-supervised methods have nevertheless been adapted to PU learning.
  • One-class classification: One-class classification identifies one class against the entire population, while PU learning defines its domain through the unlabeled data.Unlabeled data can reveal low-density regions likely to be negative, and the negative class may be too diverse for representative labeling.
  • Label noise: PU learning is often interpreted as one-sided label noise, where positive examples can be incorrectly labeled as negative.Under SCAR, the positive and negative mislabeling probabilities are 1 − c and 0, respectively; related methods include rebalancing and empirical-risk minimization.
  • Missing data: PU labeling mechanisms parallel missing-data taxonomies, but SCAR and SAR correspond to MNAR rather than MCAR or MAR within that taxonomy.Their class values have different probabilities of being missing, so the analogy does not imply identical missingness categories.
  • Multiple-instance learning: Multiple-instance learning can be phrased as PU or NU learning because positive bags may contain mixed examples while negative bags provide known negatives.A bag is positive when at least one instance is positive and negative otherwise.

9 Conclusions and Perspectives

The survey organizes PU learning around formal settings, assumptions, class-prior estimation, modeling, evaluation, applications, and relations to other machine-learning areas. It concludes that realistic labeling, empirical evaluation, PU benchmarks, and relational learning remain important priorities.

  • Questions Revisited: PU learning uses either a single-training-set scenario or a case-control scenario with independently drawn unlabeled and positive datasets.The single-training-set setting labels a subset of positives from one i.i.d. sample; case-control uses an i.i.d. population sample plus a positive-distribution sample.
  • Questions Revisited: Common assumptions concern data distributions or labeling mechanisms, including separability, smoothness, SCAR, and the more realistic SAR assumption.SCAR assumes labels are selected completely at random, whereas SAR allows labeling to depend on attributes.
  • Questions Revisited: Class-prior estimates support PU model design by weighting data or modifying algorithms to represent expected positive and negative counts.The survey describes multiple estimation techniques and connects the estimated prior to class-prior incorporation methods.
  • Questions Revisited: PU evaluation uses either estimated-prior bounds for traditional metrics or metrics computed from observed information as proxies.Both approaches exploit SCAR, and evaluation receives comparatively less attention than other PU-learning questions.
  • Questions Revisited: PU data arises when only positive information is recorded, people under-report or deceive, or one class is easier to identify than another.Examples include medical records, knowledge bases, stigmatized survey responses, bioinformatics, and remote sensing.
  • Future Directions: The survey identifies realistic labeling mechanisms, broad empirical comparisons, PU-native evaluation, real-world benchmarks, and relational-domain methods as future directions.Existing work often relies on SCAR, small or converted datasets, fully labeled test sets, and propositional rather than relational data.
Loading 1811.04820v3…