オンライン学習

オンライン学習
Prediction Learning and Games
Ch2. Prediction with Expert Advice
専門家の助言による予測
y1 , y2 ,... Y outcom space (suffixは時刻）
pˆ 1 , pˆ 2 ,.... D decision space(suffix は時刻）　maybe Y  D
時刻 t における専門家 E  Eの予測 f E ,t  D
予測者が pˆ tで ytを予測した後に真の ytが明らかになる
ここで損失関数 l : D  Y  R
予測者の損失： l  pˆ t , yt 
専門家の損失： l  f E ,t , yt 
累積regret : RE ,n   l  pˆ t , yt   l  f E ,t , yt   Lˆn  LE ,n
n
t 1
Lˆn   l  pˆ t , yt ,
n
where
t 1
rEt  l  pˆ t , yt   l  f E ,t , yt 
LE ,n   l  f E ,t , yt 
n
t 1
n
 RE ,n   rEt
t 1
roundとはオンライン学習における１個のデータからの
推論１回分のこと
Cf. epoch とは、全データに対するroundを一回りすること
このような状況における予測者の目標はroundあたりの
regretをゼロにすること
n
1 ˆ

 Ln  min Li ,n   0
i 1, 2 ,...,N

n
cf .E  i  1,2,...,N 
予測者＝専門家の予測を平均
時刻tにおける専門家の予測の重み付き平均
w f

pˆ 
 w
N
i 1
t
i ,t 1
i ,t
N
i 1
i ,t 1
wi ,t 1 (i  1,2,.., N )はN人の専門家に割り当てられた重み
wi ,t 1これを t  1までの累積 regret Ri ,t 1を勘案して


n 
1 ˆ
目標： Ln  i min
Li ,n  0 を達成するように学習する
1, 2 ,...,N
n
Ri ,t 1  Lˆt 1  Li ,t 1なので累積損失 Li ,t 1の小さな専門家 iを選ぶ
 Ri ,t 1の大きな専門家 iの重み wi ,t 1を大きくする
 Ri ,t 1の増加関数
そこで、Ri,t-1の増加関数を、非負、凸、増加関
数  の微分  を用い、wi ,t 1   Ri ,t 1  とする
N
よって
i 1  Ri ,t 1  f i ,t
pˆ t 
  R
N
i 1
i ,t 1

Lemma2.1
sup  ri ,t Ri ,t 1   0
N
yt Y i 1
where
ri ,t  l  pˆ t , yt  - l  f i ,t , yt 
Lemma 2.1
sup  ri ,t Ri ,t 1   0
ri ,t  l  pˆ t , yt  - l  f i ,t , yt 
N
yt Y
where
i 1
   R  f

 Ri ,t 1 l  pˆ t , yt 

i
,
t

1
i
,
t
 i 1

i 1
 l  pˆ t , yt   l  N
, yt ※
N
 Ri ,t 1 
   Ri ,t 1 


 i 1

i 1
N
Proof.
N
  R
N
by Jensen' s inequality  ※ 
i 1
l  f , y 
  R 
i ,t 1
i ,t
t
N
i 1
i ,t 1
  l  pˆ t , yt  - l  f i ,t , yt  Ri ,t 1    ri ,t Ri ,t 1   0
N
N
i 1
i 1
Regret vectorの記法
時刻tのinstantaneous regret vector: r  r ,.....,r 
 時刻Tまでの累積regret vector: R   r
potential function:
 R      R  where R   r
t
1,t
T
T
i 1
t
t 1
N
t 1
t 1
i ,t 1
i ,t 1
 1 i ,
 : C2 , non - negative, strictly increasing , concave
 : C2 , non - negative, increasing , convex


    
重み付き平均予測者：
R  f


 R 
N
pˆ t
i 1
N
i 1
t 1 i
t 1 i
i ,t
where R t 1 i 
R t 1  R t 1  R t 1

Ri ,t 1
R t 1 Ri ,t 1
N ,t
Potential functionを用いた定理
Blackwell条件：Lemma2.1のΦによる表現
sup r   R   0
yt Y
t 1
t
定理2.1: 予測者がpotential function
 u      u  に対してBlackwell条件を満
たしているとき
N
i 1
i
1 T
 R T    0   t 1 C rt  for all T
2
N
N

where
C rt   sup i 1  ui i 1  ui ri ,2t
uR N
定理2.1の証明
 R t を  R t 1 の周りで Taylor展開すると
 R t    R t 1  rt 
1 N N 2
  R t 1    R t 1   rt   
r i ,t rj ,t
2 i 1 j 1 ui u j 
この項はBlackwell条件
より≤０なので
where はR N内のあるベクトル
1 N N 2
  R t 1    
r i ,t rj ,t
2 i 1 j 1 ui u j 
2
r i ,t rj ,t


i 1 j 1 u u
i
j 
N
N
 2 f g  x    f   g 
cf . 
 f   g   f   g 
2
x
x
N
N
N
N
N




  i 1  i i 1  j 1  i   j ri ,t rj ,t   i 1  i i 1  i ri ,2t
  i 1  i i 1  i ri ,t    i 1  i i 1  i ri ,2t
N
N
2
N
N
ΨがConcaveなのでこの項 ≤０だから
N
N

  i 1  i i 1  i ri ,2t  C rt
1
これで  R t    R t 1   C rt
2
が言えたので、


後はこれを t  1,2,..,Tまで繰り返せばよい。
■
定理2.1の利用
Regret: Ri,nの上限を与える




 max R n       max Ri ,n     max
 Ri ,n  ※
i 1,..,N
  i 1,..,N  
N
 concave ※  i 1  Ri ,n    R n 
 max Ri ,n   1  1  R n 
i 1,..,N
これに定理2.1を組み合わせれば
1 n
 

max Ri ,n   1  1 R n    1  1  0  t 1 C rt  
i 1,..,N
2

 
定理2.1の利用：
多項式重み平均予測者
 p u  

wi ,t 1   p
pˆ t
2 p
p
t 1 

p
i 
i 1
where
  R
u    u  2
ui は uiのうち正のもの
 R t 1   R t 1  R t 1
R  

N
2 p
t 1 i
p
Ri ,t 1
2Ri ,t 1  
p 1
2Ri ,t 1 
R t 1
p 1
R t 1 
p2

2

l  pˆ , y  - l  f , y 



  l  pˆ , y  - l  f , y 
N
t 1
i 1
s 1
N
t 1
i 1
s 1
Ri ,t 1
p 1
s
s
s
i,s
s
i,s
s

s
f i ,t
p 1

 R 
p 2
p
p
Corolloary 2.1
損失関数lは凸（convex)で[0,1]区間の値をと
り、最小値＝０。このとき
Proof.
2 p
ˆ


Ln  min
L

n
p

1
N
i
,
n
i 1,...,N
1
1
 R n 

Lˆn  min
L

max
R



i ,n 定義より i 1,..,N
i ,n
i 1,...,N
1 n
 1 


n


1 
1  1
     0   t 1 C rt       t 1 C rt  ※
2


 
 2
  0   0と定理 2.1
1
さらに  ( x )  x p   1 ( x )  x1 p , ( x )  x 2 p   1 ( x )  x p 2
  
1
1
 x   x
12
 ※  1 2 t 1 C rt 
n
12
  x   xp    x   p  p  1xp2
  x   x 2 / p    x  
2
px  p2  / p
  u r  p( p  1) u  r ※※※
N
i 1
i
2
N
i ,t
i 1
p 2
i


i ,t
  y 
p 1/ p
Hoelder の不等式  xy   x
※※※  p( p  1) i 1 ui 

p 2
N

2

p
( p 2 )
q 1/ q


( p 2 ) / p

where p 1  q 1  1より
N
i 1
ri ,t

p 2/ p
かくして 1 2 t 1 C rt   1 2 t 1 sup i 1  ui i 1  ui ri ,2t
n
12
n
N
N
uR N

2
n
 N u p2  ( p2 ) 
 1 2 t 1
p
(
p

1
)
i 1
i 
p  p 2  / p
N






p
u
i1 i 

p
 n
1
 N u p 2  ( p2 ) 

  t 1 N
(
p

1
)
i 1
i 
p  p 2  / p


i1 ui  

p


 t 1 ( p  1) i 1 ri ,t
n
N
   
12
p 2/ p
( p  1)i 11
t 1
n
N
( p 2 ) / p
( p 2 ) / p
i 1

N
i 1
 
12
p 2/ p
=N

N
ri ,t

p 2/ p

12
ri ,t

12
p 2/ p
12




 n( p  1) N
2
p




定理2.1の利用
指数重み平均予測者
 u  
1

 
N
ln  eu
i
i 1
wi ,t 1   R t 1 i 
Ri ,t 1
e
 j1 e
R j ,t 1
N
exp  Lˆ  L

pˆ 
 exp  Lˆ  L
N
j 1
t
t 1
N
j 1
t 1
i ,t 1
 f

j ,t 1
i ,t
exp  L  f


 exp  L 
wi ,t 1 exp  l  f i ,t , yt 
wi ,t  N
 j1 w j ,t 1 exp  l  f j ,t , yt 
N
j 1
i ,t 1
N
j 1
j ,t 1
i ,t
Corolloary 2.2
損失関数lは凸（convex)で[0,1]区間の値をと
り、最小値＝０。η>0に対して
Proof.
ln N n
ˆ
Ln  min Li ,n 

i 1,...,N

2
1
1
 R n 

Lˆn  min
L

max
R



i ,n 定義より i 1,..,N
i ,n
i 1,...,N
 1  ln N 1 n
1 n

 1 


1
     0   t 1 C rt      
 t 1 C rt  ※
2
2

 

  
ln N
  0  
と定理 2.1
1

1
1
さらに  ( x )  ex   1 ( x )  ln x, ( x )  ln x   1 ( x )  ex


 ln N 1 n

  1  1  x   x  ※  
 t 1 C rt 
2
 

1
1
x
2 x
  x   e    x    e
  x   ln x    x  

x
1
N
u 2
2
 iN1  ui iN1  ui ri ,2t 

e
i1 ri ,t  
N
u
 i 1 e
i
i
 損失関数lは[0,1]区間だから、 0  ri ,2t  l  pˆ t , yt  - l  f i ,t , yt   1
2
かくして 1 2 t 1 C rt  
n
※
ln N


n
2
n
2
指数重み平均予測者の最適上限
：定理2.2
 最適上限は以下の式であり、3.7節でこれを改善することが
できないことが示される。
ln N n
ˆ
Ln  min Li ,n 

i 1,...,N

8
 定理2.2は、以下の補題を使えば比較的簡単に証明できる。
 Lemma2.2
X　is a random variable: a  X  b, for any s  R
s (b  a)
ln E[e ]  sE[ X ] 
8
2
sX
2
proof of Lemma2.2
 


ln E e sx  sE x   ln E e s  x E  x  だから E x   0, a  x  bに対して
 
だから E x   0, a  x  bに対して E e
sx
e
s 2 b  a 2
8
を言えばよい
x  a sb b  x sa
e 
e
ba
ba
b sa
a sb def  ( u )
sx
E x   0  E e 
e 
e e
ba
ba
a
where e (u )  1  p  peu e  pu , p  
, u  s (b  a )
ba
p
 u   ln 1  p  peu  pu, u    p 
  0   0,  0   0
u
p  (1  p )e
exp is c onvex e sx 
 


 u  


p (1  p )e u
 p  (1  p)e 
u 2

1
4
1 2
u 2 s 2 b  a 
by　Taylor　 u    0   u 0   u  0  

2
8
8
2
ηの時間依存性を除く
定理2.3
第1引数に対して convexな損失関数 lは[0,1]区間の値をとる。
For all n( 1), and for all y1,..,yn  Y , 指数重み平均予測において、
t  8ln N  / tとしたとき
n
ln N
ˆ
Ln  min
Li ,n  2 ln N 
i 1,..,N
2
8
Lemma 2.3
N  2,     0, d1 ,...,d n  0 such thati 1 e di  1
N
d i
e
i1
N
ln
 j 1 e
N
 d j

 
ln N

最も優秀＝最少損失のexpertが知られている場合
 半数以上が損失＝０のexpertなら、多数決で半数ず
つ損失≠0のexpertを排除していくことによってlogN回
で収束する。
 もう少し一般化すると
 定理2.4
Ln  min
Li ,n が予め知られている
i 1,..,N
なら、
第1引数に対して convexな損失関数 lは[0,1]区間の値をとる。
For all n(  1), and for any に対して指数重み平均予測において
Lˆn 
Ln  ln N
1  e 
proof of T h.2.4
wi ,t 1
X tは確率
で値 l  fi ,t , yt をとる確率変数とする
Wt 1
 Ln  ln N  ln
i1 wi,t 1e
N
ln

n
n
Wn
W
  ln t   ln
W 0 t 1 W t 1 t 1
l  fi ,t , yt 
 
 ln E e Xt
N
w
i 1 i ,t 1
 Ln  ln N   ln

t 1
N
i 1

e
l  fi ,t , yt 
wi ,t 1
N
i 1

Lemma A.3
i1 wi,t 1e
N
n

i1 wi,t 1e
N
。
l  fi ,t , yt 
wi ,t 1



 1 E X t   e  1 l  pˆ t , yt 

Jensen


P roof of Lemma3
by convexitye sx  xes  1  x e0  xes  1  x 
where 0  x  1
 Ex e   Ex x e  1  Ex x   ee 1E x   ln E e sx   e s  1E x 
sx
)1  z  e z
s
s


z  e s  1 E x 

n
 e   1 t 1 l  pˆ t , yt   e   1 Lˆ
Colloary 2.4

2 ln N 



  ln 1 
where
L
 0は予め知られているとき
n


Ln 

Lˆn  Ln  2 Ln ln N  ln N
損失の微分を用いる予測者
指数重み予測の重みwi,t-1の定義中に現れる
累積損失を累積損失の勾配（微分）に置き換
える
 exp    l  pˆ , y   f  f
pˆ 
 exp    l  pˆ , y   f 
t
N
t 1
i 1
s 1
s
N
t 1
j 1
s 1
s
s
i ,s
s
i ,t
j ,s
Colloary 2.5
decision space D is a convex subset of the q  R d : q  1.
損失関数lはconvexで l  1,
重みwi ,t 1  exp   s1 l  pˆ s , ys   f i ,s を用いた予測者は次式を満たす
t 1
ln N n
Lˆn  min
L


i ,n
i 1,...,N

2
損失の微分を用いる予測者
 指数重み予測の重みwi,t-1の定義中に現れる累積損
失を累積損失の勾配（微分）に置き換える
exp    l  pˆ , y   f  f

pˆ 
 exp    l  pˆ , y   f 
t
N
t 1
i 1
s 1
s
N
t 1
j 1
s 1
s
s
i ,s
s
i ,t
j ,s
Colloary 2.5
decision space D is a convex subset of the q  R d : q  1.
損失関数lはconvexで l  1,
重みwi ,t 1  exp   s1 l  pˆ s , ys   f i ,s を用いた予測者は次式を満たす
t 1
ln N n
ˆ
Ln  min
Li ,n 

i 1,...,N

2
Colloary 2.5
重みwi ,t 1  exp   s1 l  pˆ s , ys   f i ,s を用いた予測者は次式を満たす
t 1
ln N n
Lˆn  min
L


i ,n
i 1,...,N

2
proof：　l q, yt   q  l  pˆ t , yt を [0,1]にスケール変換 後述 した後、
定理 2.2を用いれば、
max
t 1  pˆ t  f i ,t   l  pˆ t , yt   t 1 l  pˆ t , yt   min
t 1 l  f i ,t , yt 
i 1 ,..,N
i 1 ,..,N
n
n
n
n



2
l  f i ,t , yt を l  pˆ t , yt の周辺で展開し、
ln N
l  pˆ t , yt   l  f i ,t , yt   t 1  pˆ t  f i ,t   l  pˆ t , yt から
n
ln N n
n
n






ˆ
Lˆn  min
L

l
p
,
y

min
l
f
,
y

 ■


t 1
t 1
i ,n
t
t
i ,t
t
i 1,...,N
i 1 ,..,N

2
スケール変換
l  0, M の場合 l
M
とすれば大体 l  0,1の場合の解析が使える。
Colloary2.4の Lˆn  Ln  2 Ln ln N  ln Nを lを l
M
とすれば
Lˆn Ln
Ln

 2 ln N  ln Nなので両辺を M倍すれば
M M
M
損失関数がM倍されているので当然
Lˆn  Ln  2 Ln M ln N  M ln N
payoff（利得）の最大化
payoff関数 h : D  Y  R, pˆ t


N
i 1
wi ,t 1 fi ,t
Wt 1
whereWt 1  i1 wi ,t 1
h [ M , )  is concaocavefor1st argument,
n
ln N
ˆ
and 0    1 2M , then H in  H n 
  t 1 h fi ,t , yt 
定理2.5

n
ˆ
where H n  t 1 h pˆ t , yt , cf. H  max H in  max t 1 h f i ,t , yt 
*
n
n
i 1,..,N
i 1,..,N
N
Regretが減衰する場合
「現在の損失のほうが過去の損失より大切」
というのはreasonable
この考え方での累積損失を分析する
0  1   2  ri ,t  l  pˆ t , yt   l  fi ,t , yt 


平均減衰累積regret : max
 
n
i 1,..,N
t 1
n
t 1
これをできるだけ小さ
r
nt i ,t
nt
くしたい
定理2.7 平均減衰累積regretの下限
各nに対して outcomey1 , y2があり、 2つのexperti, i( i )が
i  arg min l  f j ,n , y1 , i  arg min l  f j ,n , y2 かつ
j
j
c  0　, min y  y , y l  fi ,n , y   l  fi,n , y   cのとき
1
2
if t 0 t   thenC , 任意のforcasting戦略に対して



noutcom eの系列 max
 
n
i 1,..,N
t 1
n
t 1
r
n t i ,t
n t
C
定理2.8平均減衰累積regretの上限（多項式
重みの予測者の場合）
  r  f

pˆ 
   r 
N
t 1
i 1
s 1 i , s
t
N
t 1
i 1
s 1 i , s
i ,s
where   x   ( p  1) x p
平均減衰 regret は下式を満たす
2

r



t 1
t 1
n  t i ,t
n t
max

2
e
ln
N
n
n
i 1,..,N
t 1  nt
t 1  nt
n
 nt ri ,t
2e ln N


t 1
特に　if t 0  t   then max

n
n
i 1,..,N

t 1 nt
t 1  nt
n
n
 t  t  1 の場合以下が言える
a
 O 1 / log n 
n
 O n a 1 

r
t 1 nt i ,t  
max

n
i 1,..,N
t 1  nt O log n  / n
 O 1 / n



if a  1

if 1/2  a  1
if a  1 / 2
if a  1 / 2

Download Report