オンライン予測理論

オンライン予測理論
第４回
システム情報科学研究院・情報学部門
瀧本 英二
これまでのおさらい
オンライン予測
─ エキスパート予測の統合
乱択プロトコル
xt2 {0,1}N
各時刻 t = 1, 2, 3, ..., T において
問題 Qt
答え yt
③
2 {0,1}
①
統合
アルゴリズム
②
zt 2{0,1}
1
エ
キ
2 ス
パ
ー
ト
N
一意に定まる
統合アルゴリズム
f : ((x1,y1), ...,(xt-1,yt-1), xt)  pt = Pr(zt = 1)
これまでの履歴
現在のエキスパート達の出力
c乱択二分法
仮定：全問正解のエキスパートが存在
• Wt = 時刻 t – 1 まで全問正解のエキスパート数
• kt = そのうち “1” と予測したエキスパート数
pt
1
kt / Wt
0
c
1–c 1
c
誤り回数
1/2
log2 N
0
loge N
1 – ln 2
2
(log2 N) / 2
保存的二分法（conservative halving algo)
アルゴリズムが正解したとき（yt = zt を満たす時刻 t）は
間違えたエキスパートを殺さない決定性二分法
つまり
旧： Wt = 「時刻 t – 1 まで全問正解のエキスパート数」
新： Wt = 「ys ≠ zs, 1 ·s ·t – 1 を満たす全ての
時刻 s において正解したエキスパート数」
アルゴリズムの誤り回数は，高々 log2 N
今日のテーマ
「N人のエキスパートのうち，少なくとも１人は
高々 k 回しか間違えない」
のように仮定を緩めた場合の戦略を考えよ．
まず，N=8, k=1 の場合について考えよう．
二分法の素朴な拡張はどうか
「今までの誤り回数が 1 回以下の
エキスパートの中で多数決」
問題：最大で何回間違える？
二分法の素朴な拡張はどうか
一般の場合：
（最適なエキスパートの誤り回数が高々 k 回）
「今までの誤り回数が k 回以下の
エキスパートの中で多数決」
？回以上間違える
Binomial Weight Algorithm
（二分法への還元）
N. Cesa-Bianchi, Y. Freund, D. Helmbold, M. Warmuth,
On-line Prediction and Conversion Strategies,
Machine Learning, 25, 71-100, 1996
N=8, k=1 のとき，誤り回数 5 回以下
還元のアイディア（ver. 1）
• 仮想エキスパート Ei,A を導入
(1 · i · N, A µ {1, 2, ..., T}, |A| · k)
• 時刻 t のとき，Ei,A は
t 2 A ) エキスパート i と同じ予測
t 2 A ) エキスパート i の予測を反転
• 仮想エキスパートの１人は全問正解！
• 仮想エキスパート上で二分法を実行
仮想エキスパート Ei,A
コピーたち
1,4,7
オリジナルの
エキスパート i
3,6
・
・
・
いつもエキスパート i と
同じ予測をするよ
時刻 t = 1, 4, 7 のときだけ
エキスパート i と違う予測
をするよ
時刻 t = 3, 6 のときだけ
エキスパート i と違う予測
をするよ
例（N = 2, k=2, T = 4）
yt
xt,2
エキスパート 2
E2,
E2,{1}
E2,{2}
E2,{3}
E2,{4}
E2,{1,2}
E2,{1,3}
E2,{1,4}
E2,{2,3}
E2,{2,4}
E2,{3,4}
二分法
アルゴリズム
zt
仮想エキスパート 22人
E1,
E1,{1}
E1,{2}
E1,{3}
E1,{4}
E1,{1,2}
E1,{1,3}
E1,{1,4}
E1,{2,3}
E1,{2,4}
E1,{3,4}
xt,1
エキスパート 1
動作例： t = 1
yt = 1
0
エキスパート 2
E2,
E2,{1}
E2,{2}
E2,{3}
E2,{4}
E2,{1,2}
E2,{1,3}
E2,{1,4}
E2,{2,3}
E2,{2,4}
E2,{3,4}
X0
X
X
X
X
X
X
1
0
0
0
1
1
1
0
0
0
二分法
アルゴリズム
1
0
1
1
1
0
0
0
1
1
1
zt = 1
X
X
X
X
E1,
E1,{1}
E1,{2}
E1,{3}
E1,{4}
E1,{1,2}
E1,{1,3}
E1,{1,4}
E1,{2,3}
E1,{2,4}
E1,{3,4}
1
エキスパート 1
動作例： t = 2
yt = 1
1
エキスパート 2
E2,
E2,{1}
E2,{2}
E2,{3}
E2,{4}
E2,{1,2}
E2,{1,3}
E2,{1,4}
E2,{2,3}
E2,{2,4}
E2,{3,4}
X
1
1
X
X
X
X0
1
1
X
X
X
X
0
X
1
1
二分法
アルゴリズム
X
X
X
0 X
0 X
1
zt = 1
E1,
E1,{1}
E1,{2}
E1,{3}
E1,{4}
E1,{1,2}
E1,{1,3}
E1,{1,4}
E1,{2,3}
E1,{2,4}
E1,{3,4}
1
エキスパート 1
動作例： t = 3
yt = 1
0
エキスパート 2
E2,
E2,{1}
E2,{2}
E2,{3}
E2,{4}
E2,{1,2}
E2,{1,3}
E2,{1,4}
E2,{2,3}
E2,{2,4}
E2,{3,4}
X
X0
X
X
X
X
X
X
X
X
1
0
1
X
X
0
X
1
二分法
アルゴリズム
X
X
X
X
X
0 X
zt = 0
E1,
E1,{1}
E1,{2}
E1,{3}
E1,{4}
E1,{1,2}
E1,{1,3}
E1,{1,4}
E1,{2,3}
E1,{2,4}
E1,{3,4}
1
エキスパート 1
解析
• 仮想エキスパート数
• 誤り回数 (k ≧ 3 のとき）
問題点
1. アルゴリズムが T を知っている必要がある
2. 各時刻の計算時間と誤り回数の上界が
T に依存
•各時刻における計算時間を O(N) にできる
•誤り回数の上界も改善可能
Binomial Weighting Algorithm
アルゴリズムの改良について
• 計算量の改善
生き残っている仮想エキスパート数と，
その中で “1” と予想しているエキスパート数
さえ計算できればよい
演習
エキスパート i が，時刻 t - 1 までに li (≦ k）回間違え
ており，時刻 t で “0” と予想したとする．
1. 生き残っている仮想エキスパート Ei,A の数は？
2. その中で “1”と予想している仮想エキスパート数は？
アルゴリズムの改良について
• 誤り回数の改善
「保存的二分法」の利用：
アルゴリズムが正解した回は，エキスパートを殺さない
解析上，アルゴリズムが正解した
時刻は存在しなかったことと等価
m = アルゴリズムの誤り回数の上界
とするとき，T = m と考えて良い
解析
• 仮想エキスパート数
• 誤り回数の上界
を満たす最大の m
定理：