Budgeted stream-based active learning
via adaptive submodular maximization
Kaito Fujii (UTokyo)(joint work with Hisashi Kashima (KyotoU))

IBIS Workshop
2017.11.8

1/ 23

Table of Contents
1

Application: Pool-/Stream-based Active Learning

2

Previous Work: Adaptive Submodular Maximization

3

Previous Work: Submodular Secretary Problem

4

Proposed Framework

5

Experiments
2/ 23

Supervised Classiﬁcation
Input
Input

A set of labeled instances {(xi , yi ) ∈ X × Y}i=1,··· ,nOutputOutputA classiﬁer f̂ : X → Y
X = R2 ,Y = {red, blue}3/ 23

Supervised Classiﬁcation
Input
Input

A set of labeled instances {(xi , yi ) ∈ X × Y}i=1,··· ,nOutput
OutputA classiﬁer f̂ : X → Y
X = R2 ,Y = {red, blue}

3/ 23

Motivation for Active Learning
In some real world scenarios,
there are a lot of unlabeled instances, butlabeling needs a large cost (money or time).

ActiveActive Learning
Learning

The learner selects which instances to label
and can reduce the labeling cost.

4/ 23

Pool-based Active Learning
All unlabeled instances are given in advance

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y
5/ 23

Pool-based Active Learning
All unlabeled instances are given in advance

7→ redUnlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y
5/ 23

Pool-based Active Learning
All unlabeled instances are given in advance7→ blue

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y
5/ 23

Pool-based Active Learning
All unlabeled instances are given in advance7→ blue

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y
5/ 23

Pool-based Active Learning
All unlabeled instances are given in advance

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y
5/ 23

Pool-based Active Learning
All unlabeled instances are given in advance

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y
5/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y

6/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y

6/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)
7→ blue

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ XLabeling oracle
φ: V → Y

6/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y

6/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)
7→ redUnlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y

6/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y

6/ 23

Stream-based Active Learning
Unlabeled instances arrive sequentially
We consider the case of selecting k instances out of n(n, k known in advance)

Unlabeled instances
V = {xi }i=1,··· ,n ⊂ X

Labeling oracle
φ: V → Y

6/ 23

Overview
A new framework for stream-based active learning
Pool-based active learning

Stream-based active learning

Adaptive submodularmaximization

Proposed framework

All unlabeled instances are
given in advance[Golovin–Krause’11]

Unlabeled instances appear
one by one

Submodular secretary problem[Bateni–Hajiaghayi–Zadimoghaddam’13]

7/ 23

Table of Contents
1

Application: Pool-/Stream-based Active Learning

2

Previous Work: Adaptive Submodular Maximization

3

Previous Work: Submodular Secretary Problem

4

Proposed Framework

5

Experiments
8/ 23

Submodular Maximization
Selection of a “good” subset of given ﬁnite set VMaximize

subject tof (S)f : 2V → R
submodular|S| ≤ k

Data
Data Summarization
Summarization[Badanidiyuru+’14]

Select a small summary for given large dataset V

f


>

f




9/ 23

Adaptive Submodular Maximization[Golovin–Krause’11]

Selectan instanceObserve
its label

The learner can select the next instance to label
according to the labels observed so far
Adaptive
Adaptive Submodularity
Submodularity

An extention of submodularity to this adaptive setting
10/ 23

Table of Contents
1

Application: Pool-/Stream-based Active Learning

2

Previous Work: Adaptive Submodular Maximization

3

Previous Work: Submodular Secretary Problem

4

Proposed Framework

5

Experiments
11/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ e

12/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ en = 103

12/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ en = 1034

12/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ en = 10347

12/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ en = 10347612/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ en = 1034

76912/ 23

Classical Secretary Problem [folklore’60s]
Problem
Problemn candidates arrive in random order (n is given),and decide whether to hire at each arrival

Classical
Classical Secretary
Secretary Algorithm
Algorithm

pass the ﬁrst ⌊n/ e⌋ ones, and after that,
if the coming one is the best so far, hire him
the best one can be hired with prob. ≥ 1/ en = 10347

6945802

12/ 23

Submodular Secretary Problem[Bateni–Hajiaghayi–Zadimoghaddam’13]

A generalization of the classical secretary problem
1

multiple candidates can be selected2

the objective function f : 2V → R≥0 is submodular
n = 10, k = 3

13/ 23

Competitive Ratio

The competitive ratio of an algorithm is α ∈ [0, 1].
def

For any problem instance, the output S satisﬁes:

E[f (S)] ≥ α maxS∗ ⊆V f (S∗ )the optimal achieved by the clairvoyant
14/ 23

Table of Contents
1

Application: Pool-/Stream-based Active Learning2Previous Work: Adaptive Submodular Maximization

3

Previous Work: Submodular Secretary Problem

4

Proposed Framework

5Experiments
15/ 23

Proposed Framework
The proposed framework is a combination ofprevious frameworks, but it is not straightforward
Adaptive SubmodularMaximization

Submodular SecretaryProblem
New property:
Policy-Adaptive Submodularity

Proposed Framework
16/ 23

Policy-Adaptive Submodularity
Policy-adaptive submodularity is also a naturalextension of submodularity to the adaptive setting
Submodularity

Diminishing returnof each instanceto the adaptive setting
Adaptive
Submodulairty
17/ 23

Policy-Adaptive Submodularity
Policy-adaptive submodularity is also a naturalextension of submodularity to the adaptive setting
Submodularity

Diminishing returnof each instanceDiminishing returnof each set

to the adaptive setting
Adaptive
Submodulairty
17/ 23

Policy-Adaptive Submodularity
Policy-adaptive submodularity is also a naturalextension of submodularity to the adaptive setting
Submodularity

Diminishing returnof each instanceDiminishing returnof each set

to the adaptive setting
Adaptive
Submodulairty

Policy-Adaptive
Submodularity
17/ 23

Adaptive Stream AlgorithmStream setting

A limited
Streammemory
settingcan be used

Partition the whole stream into k segments,and select the “best” instance from each segmentn/ k instancesn/ k instancesn/ k instancesmax∆(v|ψ0 )max∆(v|ψ1 )max∆(v|ψ2 )Theorem [Fujii–Kashima’16]

The competitive ratio is (2 −p···t3)(1 − 1/ e) ≈ 0.16
18/ 23

Adaptive Secretary Algorithm
Secretary setting Secretary
immediatesetting
decision at each arrival

Apply the classical secretary algo. to each segment,
and select the “best” instance with probability 1/ e
n/ k instancesn/ k instancesn/ k instancesmax∆(v|ψ0 )with prob. 1emax∆(v|ψ1 )with prob. 1emax∆(v|ψ2 )with prob. 1e

Theorem [Fujii–Kashima’16]
The competitive ratio is2e1−1/ ep

1+2/ e≈ 0.08···t

19/ 23

Table of Contents
1

Application: Pool-/Stream-based Active Learning

2

Previous Work: Adaptive Submodular Maximization

3

Previous Work: Submodular Secretary Problem

4

Proposed Framework

5

Experiments
20/ 23

Experimental Settings
Datasets
Datasets
WDBC (n = 596，32-d)
MNIST (n = 14780，reduced to 10-d by PCA)
BenchmarksBenchmarks
Uncertainty sampling
RandomThe proposed method is based on ALuMA [Gonen+13]

21/ 23

Experimental Results
0.14

0.030

0.12

0.025

0.10

Error rate

Error rate

0.020

0.08

0.015

0.06

0.010

0.04

0.005

0.02
0.00

k = 30k = 40k = 50
Budget on the number of queries

WDBC

0.000

k = 30k = 40k = 50
Budget on the number of queries

The proposed method outperforms
uncertainty sampling in each setting

MNIST

randompool uncertainty
pool submodular
stream uncertainty
stream submodular
secretary uncertaintysecretary submodular

22/ 23

Overview
A new framework for stream-based active learning
Pool-based active learning

Stream-based active learning

Adaptive submodular
maximization

Proposed framework

All unlabeled instances are
given in advance[Golovin–Krause’11]

Unlabeled instances appear
one by one

Submodular secretary problem[Bateni–Hajiaghayi–Zadimoghaddam’13]

23/ 23