IBIS2017 11/08

1

Positive-Unlabeled Learning withNon-Negative Risk Estimator
Ryuichi
Kiryo1,2
1Gang
Niu1,2

MartinsMasashi
Christoffel du Sugiyama2,1
Plessis2

Binary classification2

Classify input data 𝑋 ∈ ℝ𝑑 to class 𝑌 ∈ +1 (positive), −1(negative)
Supervised learning:
Classifier 𝑔: ℝ𝑑 → ℝ is learned from positive data and negative dataclass:+1

class:-1: positive data: negative dataSupervised binary classification (PN learning)3

Goal: minimize expected risk
𝑅 𝑔 = 𝔼 𝑋,𝑌 ~𝑝 𝑥,𝑦 𝑙 𝑔 𝑋 , 𝑌= 𝜋p 𝔼p 𝑙 𝑔 𝑋 , +1 + 𝜋n 𝔼n 𝑙 𝑔 𝑋 , −1risk for positive class risk for negative classMinimize empirical risk: approximation by data in hand
𝜋p𝜋n𝑅෠pn 𝑔 =෍ 𝑙(𝑔 𝑥 , +1) +෍ 𝑙(𝑔 𝑥 , −1)𝑛p𝑛n𝑥∈𝒳pinput data 𝑋 ∈ ℝ𝑑class label 𝑌 ∈ ±1
loss function 𝑙: ℝ × ±1 → ℝ

𝔼p ⋅ ≔ 𝔼𝑋~𝑝 𝑥|𝑌=+1 ⋅𝔼n ⋅ ≔ 𝔼𝑋~𝑝 𝑥|𝑌=−1 ⋅𝑥∈𝒳n𝜋p ≔ 𝑝 𝑌 = +1𝜋n ≔ 𝑝 𝑌 = −1p 𝑛p 𝑖.𝑖.𝑑.

𝒳p = 𝑥𝑖 𝑖=1 ~ 𝑝 𝑥 𝑌 = +1𝑛𝑖.𝑖.𝑑.

n𝒳n = 𝑥𝑖n 𝑖=1~ 𝑝 𝑥 𝑌 = −1

Classification when negative data is unavailable
Example: click advertisement
 Clicked : positive Non-clicked : unlabeled (not interesting or unseen)

Learn a PN binary classifier frompositive and unlabeled data (PU learning)class:+1

class:-1: positive data
: unlabeled data4

Unbiased PU learning [Natarajan+, NIPS 2013, du Plessis+, ICML 2015]
Goal: minimize the same expected risk as PN learning
𝑅 𝑔 = 𝜋p 𝔼p [𝑙(𝑔 𝑋 , +1)] + 𝜋n 𝔼n [𝑙(𝑔 𝑋 , −1)]
negative data unavailable

Idea: unlabeled data = positive data + negative data
𝔼u 𝑙 𝑔 𝑋 , −1= 𝜋p 𝔼p 𝑙 𝑔 𝑋 , −1 + 𝜋n 𝔼n 𝑙 𝑔 𝑋 , −1

Risk can be expressed by only positive and unlabeled data𝑅pu 𝑔 = 𝜋p 𝔼p 𝑙 𝑔 𝑋 , +1 + 𝔼u 𝑙 𝑔 𝑋 , −1 − 𝜋p 𝔼p 𝑙 𝑔 𝑋 , −1𝔼u ⋅ = 𝔼𝑋~𝑝(𝑥) ⋅ ,𝑛𝑖.𝑖.𝑑.

u𝒳u = 𝑥𝑖u 𝑖=1~ 𝑝 𝑥 ≔ 𝜋p 𝑝 𝑥|𝑌 = +1 + 𝜋n 𝑝(𝑥|𝑌 = −1)

5

Theoretical properties of unbiased PU learning

6[du Plessis+, NIPS 2014, ICML 2015; Niu+, NIPS 2016]

Risk estimator is unbiased

𝔼 𝑅෠pu 𝑔= 𝑅pu 𝑔 = 𝑅(𝑔)For linear-in-parameter models, estimation error
vanishes in the optimal parametric rate

𝒪𝑝cf. PN learningPU learning can be better than PN learning if

𝒪𝑝𝜋p1+𝑛u𝑛p𝜋p𝜋n+𝑛n𝑛p𝜋p𝜋n1+ 𝑛 < 𝑛𝑛pun𝜋p ≔ 𝑝 𝑌 = +1 , 𝜋n ≔ 𝑝 𝑌 = −1

Unbiased PU learning works wellin linear-in-parameter models experimentally.
[du Plessis+, NIPS 2014, ICML 2015; Niu+, NIPS 2016]

𝜙(𝑥)𝑤𝑦How about flexible models, like deep nets?

From: http://book.paddlepaddle.org/02.recognize_digits/index.html

7

Unbiased PU learning with flexible model

8

unbiased PU test

Overfitting!

Error

PN-test0PN-train

unbiased PU train
Epoch (of SGD updates)

Empirical error
goes negative Classify even digits and odd digits of MNIST by 3-layer MLP
 𝑛p =100, 𝑛n =50, 𝑛u =59900

Overfitting and negative risk of unbiased PU9

If classifier can perfectly separate P and U,
training error w.r.t. 0-1 loss is:𝜋p𝑛p𝜋𝑝 ⋅ 0σ𝑥∈𝒳p 𝑙 𝑔 𝑥 , +1

1+ σ𝑥∈𝒳u 𝑙 𝑔 𝑥 , −1𝑛u0

risk for positive class−𝜋p𝑛p𝜋p ⋅ 1σ𝑥∈𝒳p 𝑙 𝑔 𝑥 , −1risk for negative classClass:+1

Class:-1: P data
: U data<0PU learning with non-negative risk estimator（non-negative PU learning）

10

Idea:

Round-up risk for negative class to zero
We propose the new risk estimator which is always non-negative𝑅෨ pu 𝑔 =𝜋p𝜋p1
෍ 𝑙 𝑔 𝑥 , +1 + 𝐦𝐚𝐱 𝟎,
෍ 𝑙 𝑔 𝑥 , −1 −
෍ 𝑙 𝑔 𝑥 , −1𝑛p𝑛u𝑛p𝑥∈𝒳pclassifier 𝑔: ℝ𝑑 → ℝ
loss function 𝑙: ℝ × ±1 → ℝ𝑥∈𝒳u𝜋p ≔ 𝑝 𝑌 = +1𝜋n ≔ 𝑝 𝑌 = −1𝔼n ⋅ ≔ 𝔼𝑋~𝑝 𝑥|𝑌=−1 ⋅𝑥∈𝒳pp 𝑛p 𝑖.𝑖.𝑑.

positive dataset 𝒳p = 𝑥𝑖 𝑖=1 ~ 𝑝 𝑥 𝑌 = +1
𝑛𝑖.𝑖.𝑑.

u
unlabeled dataset 𝒳u = 𝑥𝑖u 𝑖=1~ 𝑝(𝑥)Theoretical analysis of non-negative PU learning

11

Risk estimator is consistent and its bias decreases exponentially Bias is negligible in practice

𝒪𝑝 exp − 1Τ 𝜋p2 ൗ𝑛p + 1Τ𝑛u

Risk estimator may reduce mean squared error Non-negative risk estimator is more stable
𝔼𝒳p ,𝒳u

𝑅෨pu 𝑔 − 𝑅 𝑔non-negative PU2≤ 𝔼𝒳p ,𝒳u𝑅෠pu 𝑔 − 𝑅 𝑔2unbiased PU

For linear-in-parameter models, estimation error
vanishes in the optimal parametric rate

𝒪𝑝𝜋p1+𝑛u𝑛p

Large-scale algorithm

12•Want to use mini-batch SGD

𝒳p𝑖 , 𝒳u𝑖 : 𝑖-th mini-batch (𝑖 = 1, … , 𝑁)

•Our objective function
𝑁𝑁𝑖=1 𝑥∈𝒳𝑝𝑖

𝜋p𝜋𝑝1
෍ ෍ 𝑙 𝑔 𝑥 , +1 + max 0, ෍෍ 𝑙 𝑔 𝑥 , −1 −
෍ 𝑙 𝑔 𝑥 , −1
𝑛p𝑛𝑢
𝑛𝑝𝑖𝑖𝑥∈𝒳𝑢𝑥∈𝒳𝑝

Still, upper bound can be minimized!

•Sum of risks in mini-batches
𝑁𝜋p𝜋p1෍෍ 𝑙 𝑔 𝑥 , +1 + 𝐦𝐚𝐱 𝟎,
෍ 𝑙 𝑔 𝑥 , −1 −෍ 𝑙 𝑔 𝑥 , −1
𝑛p𝑛u
𝑛p𝑖
𝑖
𝑖=1𝑥∈𝒳p𝑥∈𝒳u𝑥∈𝒳p

CIFAR10 experimentunbiased PU test

Achieved smaller test
error than unbiased
PU and even PN!

PN test[Springenberg+, ICLR2015]

 𝑛p = 1000
 𝑛n = 562
 𝑛u = 50000

Error

Training error → 0
 P=artifacts
 N=animals
 13-layer CNN

13

non-negative PU test
PN-train
non-negative PU train

unbiased PU train

Epoch (of SGD updates)

Conclusions

14

We proposed a non-negative risk estimator for PU learning which
improves on the state-of-the-art unbiased risk estimators.
The new risk estimator is more robust against overfitting, andtraining very flexible model given limited P data becomes possible.
A large-scale PU learning algorithm was also developed.

Extensive theoretical analyses were presented.
Intensive experiments were carried out as well.

Reference15

Natarajan, Nagarajan, et al. "Learning with noisy labels." Advancesin neural information processing systems. 2013.
M. C. du Plessis, G. Niu, and M. Sugiyama. Analysis of learning frompositive and unlabeled data. In NIPS, 2014.
M. C. du Plessis, G. Niu, and M. Sugiyama. Convex formulation forlearning from positive and unlabeled data. In ICML, 2015.
G. Niu, M. C. du Plessis, T. Sakai, Y. Ma, and M. Sugiyama.
Theoretical comparisons of positive unlabeled learning against
positive-negative learning. In NIPS, 2016.
J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller. Strivingfor simplicity: The all convolutional net. 2015.