Source-linked AI summary
A bagging SVM to learn from positive and unlabeled examples
Fantine Mordelet, Jean-Philippe Vert
TL;DR
PU learning must classify positive examples when the training data contain no labeled negatives, a common issue when positives are expensive to identify. The paper proposes bagging SVM, which aggregates classifiers trained against random unlabeled subsamples for inductive and transductive learning. Experiments report performance at least as good as existing methods, with a computational advantage when unlabeled data greatly outnumber positives.
Problem
PU learning asks how to identify additional positive data from known positives and a large unlabeled pool without labeled negative examples.
Method
Bagging SVM repeatedly trains classifiers to distinguish P from random subsamples of U and aggregates them for inductive or transductive scoring.
Results
Bagging SVM performs at least as well as existing PU methods and is often faster, especially when |P| << |U|.
Takeaways & Limitations
Its practical advantage is reduced computational burden relative to biased SVM when the unlabeled set is much larger than the positive set.
Takeaways & Limitations
On real-data experiments, bagging SVM and biased SVM were not significantly different, while one-class SVM performed very well on 20 Newsgroups with fewer than 10 positives.
Abstract
from arXiv · showhide
We consider the problem of learning a binary classifier from a training set of positive and unlabeled examples, both in the inductive and in the transductive setting. This problem, often referred to as \emph{PU learning}, differs from the standard supervised classification problem by the lack of negative examples in the training set. It corresponds to an ubiquitous situation in many applications such as information retrieval or gene ranking, when we have identified a set of data of interest sharing a particular property, and we wish to automatically retrieve additional data sharing the same property among a large and easily available pool of unlabeled data. We propose a conceptually simple method, akin to bagging, to approach both inductive and transductive PU learning problems, by converting them into series of supervised binary classification problems discriminating the known positive examples from random subsamples of the unlabeled set. We empirically demonstrate the relevance of the method on simulated and real data, where it performs at least as well as existing methods while being faster.
1 Introduction
PU learning seeks to identify additional positive data when training provides known positives and unlabeled examples but no labeled negatives. The paper proposes bagging SVM for inductive and transductive settings, aggregating classifiers trained against random unlabeled subsamples.
- Motivation: The setting is common in information retrieval and gene ranking because positive examples may be costly to identify while unlabeled data are plentiful.Examples include retrieving documents related to a query and finding genes associated with a disease.
- Problem: PU learning uses a finite positive set P and an unlabeled set U to identify new positive data.Inductive learning scores any new x ∈ X, whereas transductive learning ranks only elements of U.
- Prior approach: Existing PU methods often reduce learning to discriminating positives from unlabeled data, exploiting the relationship between positive–unlabeled and positive–negative density ratios.This motivates biased SVM and weighted logistic regression approaches.
- Contribution: Bagging SVM aggregates classifiers trained to discriminate known positives from random unlabeled subsamples and adapts naturally to both PU settings.The method is presented as a simple bagging-like scheme for inductive and transductive learning.
2 Related work
Related PU-learning work addresses the absence of negatives through positive-only methods, two-step negative identification, theoretical formulations, and methods specialized to transductive ranking. Transductive PU learning has received comparatively less attention than related supervised or semi-supervised settings.
- Positive-only methods: Positive-only approaches rank unlabeled examples by similarity to positives or use one-class SVMs without treating unlabeled data as labeled negatives.These methods include mean-positive similarity ranking and more advanced one-class learning.
- Two-step methods: Two-step PU algorithms first identify likely negatives within U and then train classifiers using positives, unlabeled examples, and selected negatives.The cited approaches are described as heuristic.
- Inductive PU learning: Theoretical work has studied inductive PU learning directly, producing algorithms designed specifically for the positive-and-unlabeled setting.This line of work is distinct from simply discarding unlabeled examples.
- Transductive PU learning: Transductive PU learning is easier because the set to be screened is known, yet comparatively little work targets this setting specifically.Related transductive SVM and graph-based methods generally assume both positive and negative examples.
3 Bagging for inductive PU learning
Bagging SVM exploits classifier instability caused by varying contamination of unlabeled subsamples. It samples only U, trains classifiers against each subsample, and aggregates them while tuning subsample size K to balance accuracy and variability.
- Rationale: Discriminating positives from unlabeled data is a useful proxy because unlabeled examples contain information despite hidden positive contamination.The paper notes that positive–unlabeled density-ratio structure supports this proxy.
- Rationale: PU classifiers become especially unstable because random unlabeled samples can have different proportions of hidden positives.Low-contamination samples may yield better classifiers than highly contaminated samples, and these classifiers may be weakly correlated.
- Subsample size: Larger K tends to improve individual classifiers, whereas smaller K increases contamination variability and produces more diverse classifiers for aggregation.For a subsample of size K, the hidden-positive count is modeled as binomial with contamination rate ˆγ.
- Method: Bagging SVM trains classifiers on P versus random subsamples of U and combines their predictions, subsampling only U because P is known positive and often limited.The subsample size K is a specific parameter whose effect may require tuning.
- Aggregation: The number T of bootstrap samples is user-defined; performance generally plateaus beyond roughly 100, and simple averaging showed no significant preliminary difference from majority voting.The paper treats T and the aggregation rule as adjustable design choices.
4 Bagging SVM for transductive PU learning
The transductive extension scores each unlabeled point only with classifiers that did not use it as a negative training example. This leave-out aggregation avoids evaluating points on classifiers trained directly on them.
- Setting: Transductive bagging SVM targets scoring and ranking the known unlabeled set U rather than predicting on arbitrary future data.This setting is useful when the complete screening population is available during training.
- Caveat: Using an unlabeled point as a negative training example can produce an underestimated score, especially when the classifier fits the training data tightly.The concern reflects that consistency guarantees generally address predictions on samples outside the training set.
- Procedure: Each iteration samples U_t, trains a classifier to separate P from U_t, and assigns scores to elements outside U_t.The procedure is specified in the transductive algorithm.
- Aggregation: Each x ∈ U receives an aggregate score from classifiers whose training subsamples excluded x, with n(x) counting those usable predictions.The method aims to average predictions over sufficient classifiers for every unlabeled point.
5 Experiments
Experiments on simulated data, 20 Newsgroups, and E. coli regulatory-network inference evaluate bagging SVM against existing PU-learning and positive-only methods. Across settings, bagging SVM matches or slightly exceeds competing PU methods, with aggregation especially beneficial for small bootstrap samples.
- Simulated data: On simulated data, bagging logit slightly outperforms biased logit, while contamination generally lowers performance for both methods.The bagging method reaches at least the same performance as biased logit for some K below 50, including at high contamination.
- Simulated data: At γ = 0, bagging does not improve supervised-classification performance regardless of bootstrap-sample size.
- Simulated data: Lower K produces larger contamination variation and more dispersed individual-classifier performance, allowing aggregation to benefit from less-contaminated subsamples.For K = 10, empirical contamination ranges from 0 to 0.5, compared with 0.1 to 0.25 for K = 40.
- 20 Newsgroups: Increasing the number of bootstraps T generally improves performance until a plateau, with smaller K requiring larger T to reach it.The experiments use T = 35 for K ≤20 and T = 10 for K > 30 after preliminary tuning.
- 20 Newsgroups: On 20 Newsgroups, bagging SVM dominates the other methods for NP ≥20 and significantly outperforms biased SVM for NP > 20.For smaller NP, one-class SVM dominates, and no significant difference is established between it and bagging SVM.
- E. coli regulatory network: In E. coli regulatory-network inference, all three PU methods significantly outperform the two positive-only methods, with no significant differences among the PU methods.This result indicates that bagging SVM matches biased SVM across tested K values.
6 Discussion
The discussion presents bagging SVM as a method for inductive and transductive PU learning, motivated by aggregating classifiers trained on random unlabeled subsamples. Across the reported evaluations, it is competitive with existing methods and offers a computational advantage when unlabeled data greatly outnumber positives.
- Bagging SVM is proposed for both inductive and transductive PU learning and evaluated on simulated and real data.
- Random subsampling produces classifiers with varied contamination rates, allowing aggregation to exploit differences among individual classifiers.The sample size K controls the trade-off between the mean and variance of individual classifiers.
- The comparison is mixed: 1-class SVM can outperform PU methods with fewer than 10 training examples, and real-data differences between bagging SVM and biased SVM are not significant.This indicates that PU learning is not always better than learning from positives alone.
- For T = 35 and α = 3, bagging SVM is expected to be faster than biased SVM when U/P > 6.The complexity comparison assumes the default K = P and reflects settings with many more unlabeled than positive examples.
- Figure 7 compares precision-recall curves for baggin1 SVM, bagging5 SVM, biased SVM, 1-class SVM, and the baseline method.