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

ERATO 感謝祭 Season IV2017 年 8 月 3 日

1/ 26

目次
1

応用：プール型能動学習とストリーム型能動学習

2

既存研究：適応的劣モジュラ最大化

3

既存研究：劣モジュラ秘書問題

4

提案フレームワーク

5

実験

2/ 26

教師あり分類
入力
入力
ラベルつきサンプルの集合 {(xi , yi ) ∈ X × Y}i=1,··· ,n
出力
出力ラベルを予測する関数 f̂ : X → Y例） X = R2 ,Y = {red, blue}

3/ 26

教師あり分類
入力
入力
ラベルつきサンプルの集合 {(xi , yi ) ∈ X × Y}i=1,··· ,n
出力
出力ラベルを予測する関数 f̂ : X → Y例） X = R2 ,Y = {red, blue}

3/ 26

能動学習の動機
現実にはラベルなしサンプルはたくさん手に入るが，ラベル付与にはお金や時間がかかるという状況が多い

能動学習
能動学習
ラベルを付与するサンプルを能動的に選ぶことで，少ないラベルつきサンプルで高い予測精度

4/ 26

プール型能動学習
ラベルなしサンプルは最初にすべて与えられる

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

5/ 26

プール型能動学習
ラベルなしサンプルは最初にすべて与えられる

7→ red

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

5/ 26

プール型能動学習
ラベルなしサンプルは最初にすべて与えられる

7→ blue

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

5/ 26

プール型能動学習
ラベルなしサンプルは最初にすべて与えられる

7→ blue

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

5/ 26

プール型能動学習
ラベルなしサンプルは最初にすべて与えられる

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

5/ 26

プール型能動学習
ラベルなしサンプルは最初にすべて与えられる

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

5/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

7→ blue

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

7→ red

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

ストリーム型能動学習
ラベルなしサンプルは一つずつ現れる

n 個のうち k 個にラベル付与する設定を考える（n, k 既知）

ラベルなしサンプルの集合

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

ラベル付与オラクル

φ: V → Y

6/ 26

本研究の概要
ストリーム型能動学習のための組合せ最適化フレームワーク
プール型能動学習

ストリーム型能動学習

ラベルなしサンプルはすべて既知

サンプルはひとつずつ現れる

適応的劣モジュラ最大化[Golovin–Krause’11]

新たなフレームワーク（本研究）

劣モジュラ秘書問題[Bateni–Hajiaghayi–Zadimoghaddam’13]

7/ 26

目次
1

応用：プール型能動学習とストリーム型能動学習

2

既存研究：適応的劣モジュラ最大化

3

既存研究：劣モジュラ秘書問題

4

提案フレームワーク

5

実験

8/ 26

劣モジュラ最大化与えられた集合 V の “よい” 部分集合を探す問題

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

単調劣モジュラ関数例）データセット V を要約する部分集合を探す問題




f






>




f




9/ 26

適応的な設定

サンプルを選んだサンプルの一つ選択

ラベルを観測観測したラベルによって次に選ぶサンプルを変えられる
同じアルゴリズムでも，目的関数値が変化
適応的劣モジュラ最大化
適応的劣モジュラ最大化[Golovin–Krause’11]

オラクルに関する事前分布を考え，目的関数の期待値を最大化

10/ 26

劣モジュラ性と単調性
f (v|S) ≜ f (S ∪ {v}) − f (S)S ⊆ V に対して v ∈ V を追加したときの増分

11/ 26

劣モジュラ性と単調性
f (v|S) ≜ f (S ∪ {v}) − f (S)S ⊆ V に対して v ∈ V を追加したときの増分劣モジュラ性
劣モジュラ性 f (v|A) ≥ f (v|B) (∀A ⊆ B, ∀v ∈ V \ B)f() − f() ≥ f() − f()

11/ 26

劣モジュラ性と単調性
f (v|S) ≜ f (S ∪ {v}) − f (S)S ⊆ V に対して v ∈ V を追加したときの増分劣モジュラ性
劣モジュラ性 f (v|A) ≥ f (v|B) (∀A ⊆ B, ∀v ∈ V \ B)f() − f() ≥ f() − f()

単調性
単調性 f (v|A) ≥ 0 (∀A ⊆ V , ∀v ∈ V)f() − f()≥011/ 26

適応的劣モジュラ性と適応的単調性 [Golovin–Krause’11]∆(v|ψ)

オラクルから ψ = {(vi , yi )}i=1,··· ,ℓ を観測しているとき，新たに v ∈ V を追加した場合の増分の期待値
適応的劣モジュラ性
適応的劣モジュラ性∆(v|ψ1 ) ≥ ∆(v|ψ2 ) (∀ψ1 ⊆ ψ2 , ∀v ∈ V \ dom(ψ2 ))適応的単調性
適応的単調性∆(v|ψ) ≥ 0 (∀ψ, ∀v ∈ V)
12/ 26

目次
1

応用：プール型能動学習とストリーム型能動学習

2

既存研究：適応的劣モジュラ最大化

3

既存研究：劣モジュラ秘書問題

4

提案フレームワーク

5

実験

13/ 26

古典的秘書問題 [folklore’60s]問題問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しない
それ以降にその時点までで最良の候補が現れたら採用

1/ e 以上の確率で最良の候補を採用できる

14/ 26

古典的秘書問題 [folklore’60s]
問題
問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しない
それ以降にその時点までで最良の候補が現れたら採用

1/ e 以上の確率で最良の候補を採用できる

n = 103

14/ 26

古典的秘書問題 [folklore’60s]
問題
問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しない
それ以降にその時点までで最良の候補が現れたら採用

1/ e 以上の確率で最良の候補を採用できる

n = 1034

14/ 26古典的秘書問題 [folklore’60s]
問題
問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しない
それ以降にその時点までで最良の候補が現れたら採用

1/ e 以上の確率で最良の候補を採用できる

n = 1034714/ 26

古典的秘書問題 [folklore’60s]
問題
問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しない
それ以降にその時点までで最良の候補が現れたら採用

1/ e 以上の確率で最良の候補を採用できる

n = 10347614/ 26

古典的秘書問題 [folklore’60s]
問題
問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しないそれ以降にその時点までで最良の候補が現れたら採用1/ e 以上の確率で最良の候補を採用できる

n = 103476914/ 26

古典的秘書問題 [folklore’60s]
問題
問題
ランダムな順序で n 人の候補を面接する（n は既知）
面接したら直ちに採用するかどうか決める
アルゴリズムアルゴリズム最初の ⌊n/ e⌋ 人は採用しない
それ以降にその時点までで最良の候補が現れたら採用

1/ e 以上の確率で最良の候補を採用できる

n = 10347694580214/ 26

劣モジュラ秘書問題 [Bateni–Hajiaghayi–Zadimoghaddam’13]

ランダムな順序で現れる n 人の候補のなかから k 人を選ぶ

単調劣モジュラ関数 f : 2V → R を最大化

n = 10, k = 315/ 26

競合比α ∈ [0, 1] がアルゴリズムの競合比
def

任意の問題例について，アルゴリズムの解 S がE[f (S)] ≥ α maxS∗ ⊆V f (S∗ )を満たす

入力をすべて知っている場合の最適値

16/ 26

目次1

応用：プール型能動学習とストリーム型能動学習

2

既存研究：適応的劣モジュラ最大化

3

既存研究：劣モジュラ秘書問題

4

提案フレームワーク

5

実験

17/ 26

提案フレームワークの仮定

仮定
仮定 11

ストリームの順序にランダム性を仮定

仮定
仮定 22

全体のサンプル数 n は既知だと仮定

仮定
仮定 33

目的関数に方策適応的劣モジュラ性を仮定
適応的劣モジュラ性よりも強い性質
応用で使われる多くの関数で成り立っている

18/ 26

適応的劣モジュラ性との比較

劣モジュラ性f (A ∪ {v}) − f (A) ≥f (B ∪ {v}) − f (B)(∀A ⊆ B, v ∈ V \ B)
適応的設定に拡張
適応的劣モジュラ性∆(v|ψA ) ≥ ∆(v|ψB )(∀ψA ⊆ ψB , v ∈ V \ B)
19/ 26

適応的劣モジュラ性との比較

劣モジュラ性f (A ∪ {v}) − f (A) ≥f (B ∪ {v}) − f (B)(∀A ⊆ B, v ∈ V \ B)f (A ∪ P) − f (A) ≥f (B ∪ P) − f (B)(∀A ⊆ B, P ⊆ V \ B)

適応的設定に拡張
適応的劣モジュラ性∆(v|ψA ) ≥ ∆(v|ψB )(∀ψA ⊆ ψB , v ∈ V \ B)
19/ 26

適応的劣モジュラ性との比較

劣モジュラ性f (A ∪ {v}) − f (A) ≥f (B ∪ {v}) − f (B)(∀A ⊆ B, v ∈ V \ B)f (A ∪ P) − f (A) ≥f (B ∪ P) − f (B)(∀A ⊆ B, P ⊆ V \ B)

適応的設定に拡張適応的劣モジュラ性

方策適応的劣モジュラ性∆(v|ψA ) ≥ ∆(v|ψB )(∀ψA ⊆ ψB , v ∈ V \ B)∆(π|ψA ) ≥ ∆(π|ψB )(∀ψA ⊆ ψB , π(V) ⊆ V \ B)
19/ 26

方策適応的劣モジュラ関数の性質
補題 [Feige–Mirrokni–Vondrák’07]

f : 2V → R 劣モジュラ関数.
A(r): A ⊆ V の各要素を確率 r で含む集合.

E[f (A(r))] ≥ (1 − r)f (∅) + rf (A)20/ 26

方策適応的劣モジュラ関数の性質
補題 [Feige–Mirrokni–Vondrák’07]

f : 2V → R 劣モジュラ関数.
A(r): A ⊆ V の各要素を確率 r で含む集合.

E[f (A(r))] ≥ (1 − r)f (∅) + rf (A)

適応的設定に拡張

補題 [Fujii–Kashima’16]({fφ }φ , p) 方策適応的劣モジュラ関数.
π(r): 方策 π から各要素を確率 1 − r で削除してできる方策.

E[fφ (A(π(r), φ))] ≥ (1 − r)E[fφ (∅)] + r E[fφ (A(π, φ))]20/ 26

適応的ストリームアルゴリズム
ストリーム設定

限られたメモリの範囲でサンプルを保持

ストリーム全体を k 分割し，各部分ストリームから増分の期待値最大のサンプルを選択
n/ k samples

n/ k samples

n/ k samples

max∆(v|ψ0 )max∆(v|ψ1 )max∆(v|ψ2 )定理 [Fujii–Kashima’16]
このアルゴリズムの競合比は (2 −p···t3)(1 − 1/ e) ≈ 0.16.

21/ 26

適応的秘書アルゴリズム
秘書設定

ラベルを付与するかどうかすぐに判断

各部分ストリームに古典的秘書アルゴリズムを適用して，増分の期待値最大のサンプルを確率 1/ e で選ぶ
n/ k samples

n/ k samples

n/ k samples

max∆(v|ψ0 )with prob. 1emax∆(v|ψ1 )with prob. 1emax∆(v|ψ2 )with prob. 1e定理 [Fujii–Kashima’16]
このアルゴリズムの競合比は

2e1−1/ ep

1+2/ e≈ 0.08.

···t

22/ 26

目次1

応用：プール型能動学習とストリーム型能動学習

2

既存研究：適応的劣モジュラ最大化

3

既存研究：劣モジュラ秘書問題

4

提案フレームワーク

5

実験

23/ 26

実験設定
データセット
データセット

WDBC（n = 596，32 次元）
MNIST（n = 14780，PCA で 10 次元に削減）
比較手法
比較手法不確実性サンプリング
ランダムサンプリング
提案手法は ALuMA [Gonen+13] に基づいて設計

24/ 26

実験結果
0.140.030

0.120.025

0.10

Error rate

Error rate

0.020

0.080.015

0.06

0.010

0.040.005

0.020.00

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

WDBC0.000

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

それぞれの設定で提案手法は比較手法よりも誤差が小さい

MNIST

randompool uncertainty
pool submodular
stream uncertainty
stream submodular
secretary uncertainty
secretary submodular

25/ 26

本研究の概要
ストリーム型能動学習のための組合せ最適化フレームワーク
プール型能動学習

ストリーム型能動学習

ラベルなしサンプルはすべて既知

サンプルはひとつずつ現れる

適応的劣モジュラ最大化[Golovin–Krause’11]

新たなフレームワーク（本研究）

劣モジュラ秘書問題[Bateni–Hajiaghayi–Zadimoghaddam’13]

26/ 26