1

Accepted to ICML2017

Semi-Supervised Classification based onClassification from Positive and Unlabeled Data
1,2Tomoya Sakai, Marthinus Christoffel du Plessis,
Gang Niu,1,2 and Masashi Sugiyama 2,1
1

The University of Tokyo, Japan
2
RIKEN, Japan@IBIS2017

Classification Problem
Identify class or category of data points
Examples Image is a cat (positive class) or not (negative class)

Class: +1

Decision boundary

Class: -1

2

Supervised Learning (PN Learning)
Learn from labeled (positive and negative) data
Pattern:
Label:: positive (P) data

Class: +1
Class: -1
Decision boundary: negative (N) data

 Better performance with many labeled data Collecting labeled data is costly3Semi-Supervised Learning (SSL)
Learn from a small amount of labeled data
and a large amount of unlabeled data

: positive data
: negative data
: unlabeled data Labeling cost becomes cheap4This Work

5

Existing methods:
 Require strong distributional assumptions for utilizing
unlabeled data
Ex. the cluster assumption requires the samples
in the same cluster be likely to share the same label(Chapelle et al., NIPS, 2002)

If the distributional assumptions are not satisfied,
the performance of the existing methods decreases

Propose method: NOT require the strong distributional assumptions

Outline
1. Introduction
2. Proposed Method

3. Experiment
4. Conclusions

6

Our Idea: Use of PU Learning
Learning from positive (P) and unlabeled (U) data

: positive data
: unlabeled data
Class: +1

Unlabeled Utilize unlabeled data without the distributional
assumption (du Plessis et al., NIPS, 2014)

How to use PU learning for semi-supervised learning?

7

Our Idea (cont.): SSL Decomposition
Decompose Semi-Supervised Learning (SSL)
into PU, PN, and NU learning

P, N, and U data

PU Learning

PN Learning

NU Learning Reconstruct SSL from PU, PN, and NU learning

8

PU+NU: PUNU Learning
Since PU and NU are symmetric,
it might be natural to combine PU and NU learning

PU Learning

NU Learning

Is this really good?

9

Is PUNU Learning Better?

10From Niu et al. NIPS, (2016) , we have(Case I) The size of unlabeled data is sufficiently large
PU > PN > NU (classification accuracy)or

NU > PN > PU

 PU or NU is the best

(Case II) The size of unlabeled data is small
PN > PU > NUorPN > NU > PU

 PN is always the best PUNU (=PU+NU) is not a good idea
since it contains the worst one in the combination
 Combine PN with PU/NU would be promising(PN+PU or PN+NU is better)

Proposed Method: PNU Learning

11Combine PN with PU/NU learning (PN+PU or PN+NU)
NU Learning()

PN Learning()

PU Learning()

N and U data

P and N data

P and U data The PNU risk:

Obtain the decision rule by minimizing the PNU risk,,: classifier: risks in PN, PU, and NU learning

Comparison with Existing Methods

12

Existing approach: Design regularizer based on the distributional assumption
 Use unlabeled data for regularization

Entropy regularizer…

Manifold regularizer

Our approach:

Unlabeled data are used
: risk in supervised learning Not require the strong distributional assumptions
 Utilize unlabeled data for risk evaluation

Labeled and unlabeled data are used

Theoretical Analyses

13

Without the distributional assumptions, we prove the follows: Generalization error bound Unlabeled data help reduce the bound Optimal parametric convergence rate Variance reduction
for some if

is sufficiently large

 The PNU risk is stable in terms of the variance More stable cross-validation: risk in supervised learning: 0-1 loss

Outline
1. Introduction
2. Proposed Method

3. Experiment
4. Conclusions

14

Image Classification

15(smaller is better)
Average with the standard error of misclassification rate PNU learning outperforms the existing methods
Class-prior is estimated by
the energy distance minimization method (Kawakubo et al., IEICE-ED, 2016)* Colored cells indicate the best and comparable method in terms of t-test (sig. lev. 5%)* The methods taking 2 hours were omitted and indicated as ”N/A”

Outline
1. Introduction
2. Proposed Method

3. Experiment
4. Conclusions

16

World of SSL based on PU Learning
MRMinimization

PN

PU

Vapnik,Springer, 2000.

du Plessis et al.,
NIPS, 2014.

17

MR: misclassification rate
 Obtain classification rules based on MR minimization

SSL: Semi-Supervised Learning

World of SSL based on PU Learning
MRMinimization

18PN

PU

Semi-Supervised

Vapnik,Springer, 2000.

du Plessis et al.,
NIPS, 2014.

This talk!

MR: misclassification rate
 Obtain classification rules based on MR minimization

SSL: Semi-Supervised Learning

World of SSL based on PU Learning
PN

PU

19

Semi-Supervised

du Plessis et al.,Vapnik,MRThis talk!
NIPS, 2014.
Springer, 2000.
Minimization
AUC
Herschtal and Raskutti, Tomorrow poster session!
ICML, 2004.
Maximization
Sakai et al., MLJ, 2017.

AUC: area under the receiver operating characteristic curve Useful for imbalanced classification whenWorld of SSL based on PU Learning
PN

PU

20

Semi-Supervised

du Plessis et al.,Vapnik,
MR
This talk!
NIPS, 2014.
Springer, 2000.
Minimization
AUC
Herschtal and Raskutti, Tomorrow poster session!
ICML, 2004.
Maximization
Sakai et al., MLJ, 2017.
SMI
Suzuki et al.,Sakai et al.,
To be explored
Estimation BMC bioinform, 2009. arXiv, 2017.

SMI: squared-loss mutual information
 Statistical dependency measure Useful for dimension reduction, feature selection,independence test, and object matching

World of SSL based on PU Learning
PN

PU

21

Semi-Supervised

du Plessis et al.,Vapnik,MRThis talk!
NIPS, 2014.
Springer, 2000.
Minimization
AUC
Herschtal and Raskutti, Tomorrow poster session!
ICML, 2004.
Maximization
Sakai et al., MLJ, 2017.
SMI
Suzuki et al.,Sakai et al.,
To be explored
Estimation BMC bioinform, 2009. arXiv, 2017.

Code available athttps://github.com/t-sakai-kure/PNU