最適化と学習アルゴリズム

最適化と学習アルゴリズム
勾配降下法
直線探索
劣勾配降下法
ニュートン法
確率的勾配降下法
学習における計算効率の問題
 既に説明した回帰、識別（分類）の解法で得た閉じ
た式は逆行列計算が必要。例えば、線形回帰の場
合の正規方程式の解である重みベクトルは
w=(XTX)-1XTy
 学習データが高次元になると(XTX)の次元も大きく
なり、逆行列の計算はコストが高い（次元数の３乗）
 要は損失(=Loss)を最小化したい
 正規方程式の場合は２乗誤差だった。
逆行列計算を避けて最適化する方法が実用
上重要。
記法：損失(Loss)
入力データ： xi , 重みベクトル：
wは D次元ベクトルとする
xiに対する分類の正解： yi ( 1 or　1) ただしデータは m個あるとする
1 m
Lw    loss w　on xi , yi  
m i 1
例：
1 m
2乗損失の場合　Lw    w, xi  yi
m i 1
ヒンジ損失の場合　2
2
1 m
2
   w, xi  yi 
m i 1
1 m
Lw    1  yi w, xi 
m i 1
ここで　z   max0, z 
記法：
勾配(Gradient)とヘッセ行列（Hessian)
wは D次元ベクトルとする
pノルム：　w
p

 w1   wD
p
p

1
p
w
p
p

 w1   wD
p
p

w  w k における Lの勾配
 Lw 

Lw 


L w 
,....,
 w1
wn w  w  k  
w1  w1 k 
D
D


w  w k における Lのヘッセ行列
 
T
k 
 
HL w k 
2
  2 Lw 




L
w



w1wD w  w  k  ,w  w  k  
 w1w１ w1  w1 k 
1
1
D
D






 2

2
 Lw 
  Lw 


 wD w１ w  w  k  ,w  w  k 

wD wD w  w  k 
D
D
1
1
D
D


勾配降下法
右図で分るように
Ｌ（ｗ）が凸の場合
は、勾配▽L(w)の
逆方向に進むと
W*=argmin L(W)
に向かって進む。
図は１次元だが
実際は多次元な
ので、勾配の方
向が大切なこと
に注意
勾配
＝▽L(W)
Ｌ（w）
min L(w)
w
▽L(W*)=0
W*
定式化
• 勾配降下法(Gradient Descent)の定式化する
w：重みベクトル

Lw：重みベクトル
wのときの損失
w k  : k回目の繰り返し結果の更新された重みベクトル
最適な重みベクトル : w*  arg min Lw 
w
を求めるには勾配の逆方向に進むので下の式となる。
 
 
重みベクトルの更新式： w k 1  arg min L v  w k    k L w k 
v
L*  * ：２乗損失だと
2
2
w
 k 1

 arg min v  w
v
k 
k 
 
  L w
k 
2
2
損失を微分して０と置けば閉じた解が求まり
 
w k 1  w k    k L w k 
となる
2乗損失でないとこう簡単な式
ではない
最急降下法アルゴリズム
• L（ｗ）を最小化するようなwを求めるために、wの現在
の値w(k)から勾配▽L(w)の逆方向に進むアルゴリズム
初期値  w ( 0 ) ; k  0; w*  arg min L(w );
step1 : w ( k )が w*に十分近いなら終了
は w ( k )が w ( k 1)に十分近くて収束した）
（具体的に
step 2 : L(w ( k ) )を計算
step3 : w ( k 1)  w ( k )   k L(w ( k ) )  k は進む幅(step size)
step 4 : k  k  1　として step1へ
L ( w )  yn  w ,  ( x n )
2
2
つまり 2乗損失なら
w ( k 1)  w ( k )   k  ( yn  w ( k ) ,  (x n ) ) (x n )
最急降下法の収束の評価
前提条件
凸＆ ▽2L(w) positive
k 
 k 1
k 
 k 1




L
w

L
w

G
w

w
Lipschitz条件：
2
 
 L w  k 
テイラー展開により近似
 

2
G

w k 1  w k    k L w k  とし、 L w k＋1 を 2次のテイラー近似すると

  
 
 
 
 
  Lw    Lw   2 Lw   
Lw
 Lw     0により
Lw     Lw        Lw   
   Lw     Lw     Lw    1
k＋1
k
k
k
2
2
2
k
2
k＋1
k
k
k
2
2
k
k
2
2
k
k 1
k
2
k
2
2
 
 2 L w k 
2
直観的説明
凸かつ▽2L(w)≥0な
ので、minLに近づく
につれてこの差は
小さくなる
min L(w)
w（ｋ）
W（ｋ＋１）
  

L w k   L w k 1  G w k   w k 1
Lipshitz条件より以下のような
   
 Lw     G
2
2
Gがある
 
 L w k   L w k 1  L w k 
k
適当なGで上か
ら抑えられる
2
w k   w k 1  G w k   w k 1
2
2

k 
最急降下法の収束の評価：つづき
Lw 
k 
2
2

 
 L w k   L w k 1
 1
w k 1が w*に十分近い（ w k＋1  w* )ないし等しいとすると

k 
Lw 
k 
2
2

  
 L w k   L w*
ここで , B  w という Bを選び、 
*
2

Lipschit z条件　L w k 

  
 L w k   L w* 
B
G k

2
k 

B
とおく
G k
 G より
 G2 
BG
k
誤差を 以下にするのはオーダとして：
 BG 
O   O

 k
 B 2G 2 
 O 2 回の更新で誤差以下に収束
  
捕捉
 k をやたらと大きくする

  
と無意味！
L w k   L w*  G w k   w*
2
B  w*  B  w k   w* くらいにはなるだろう

2
  
2
 L w k   L w*  BG  G w k   w* このあたりを想定して
という雰囲気
2
という Bを選び、 
k 

B
G k
とおく
step size αを決める：直線探索
α(k)が小さすぎると収束が遅々として進まず、
大きすぎると最悪の場合最適値を飛び
越す
最適なα(k) を求める問題：直線探索

k 
k 
min
L
w


d
k 

の

 
dは降下方向(つまり  L w k  方向）
単位ベクトル　subject to  k   0
厳密に解くのは困難
直線探索の代案
k 

1 k
kの減少関数にする i.e.
 しかし、あまりにもヒューリスティック
もう少し客観的な基準として
Armijo基準とWolfe基準がある
Armijo基準とWolfe基準
ξ=0
最適値
α=0
α
行き過ぎ
L(W+α▽L(W))-L(W)
α▽L(W)
ξα▽L(W)： 0<ξ<1 予め決まった値
この不等式を満たすようにαを選ぶ：
Armijo基準
Wolfe基準：
α が小さくなりすぎないた
め。 α =0だと明らかに成
立しない(!▽L(W)Td<0)
L(W+αd)-L(W) ≤ ξα▽L(W)Td
LW T d  LW  d T d
   1
直線探索の代案:2分割法
k回目の繰り返しにおいて以下のアルゴリズ
ムでα(k)を減少させる
Step1 t=1, αt(k)=α(k)
Step2 if 停止基準(Armijo基準等）が満たされる
then return αt(k)
else αt(k)=α(k)/2
Step3 k k+1
Step4 Step 2へ
微分可能でない場合：
劣勾配(sub-gradient)の利用
凸関数 : convext : Lの subgradient


Lw   g | v  0 Lv   Lw   v  w  g
T
Lw  g | ...
w v
例
L1　loss
L w   w 1  w
 Lw  1 w  0
Lw   1,1
 L w   1 w  0
hinge　loss
Lw  1  w
 Lw  1 w  1
Lw   1,0
 L w   0 w  1
劣勾配降下法
Sub-Gradient Descent
初期値  w ( 0 ) ; k  0; w*  arg min L(w );
step1 : w ( k )が w*に十分近いなら終了
（具体的に
は w ( k )が w ( k 1)に十分近くて収束した）
step 2 sub - gradient : Lw 
 g | v  0 Lv   Lw   v  w   g　を計算
 
step3 : w k 1  arg min L v  w k    k g
v , gL  w 
step 4 : k  k  1　として step1へ　
最急降下法がうまくいかない場合
• ジグザグに動きながら最適解に近づくので収束する
速度が遅い（効率が良くない）
• 勾配以外の情報も使ってみるニュートン法
ニュートン法
 最小化したいのは損失 L(w)
 ただし、直接には最適化できない場合を考えている
 今wの現在値w(k)が与えられていて、dを加えることに
よってより最適値に近いw(k+1)を得たい。
 ここでw(k)が定数でdを変数と思って
 L(w(k+1))＝ L(w(k)＋ d)
の左辺を直接最適化する代わりに右辺を最小にする d
を求める。
 この結果をd(k)とし、よりよいLをL(w(k)＋ d(k))として、繰
り返すことによって真の最適値に近づこうとする
 ここでL(w(k)＋ d)を２次のテーラー近似する場合が
ニュートン法
2次のテーラー展開

Lw
k 
    Lw 
d  L w
k 
k 
T
 
1 T
d  d HL w k  d
2
右辺をdの関数と見て最小化しニュートン方向d(t)を求める
d
k 
 
 arg min 右辺  HL w
k 
1
 
L w k 
d
ニュートン法のアルゴリズム
step0 : k  0; 初期値  w 0 ; w*  arg min L(w );
step1 : w ( k )が w*に十分近いなら終了
   
   HLw    Lw   　  はstep size
1
dk   HL w k  L w k  を計算
step2 : ニュートン方向　step3 : w
( k 1)
w
(k )
step4 : k  k  1　として
k
step1へ
 k は直線探索で決めてもよい
k
1
k
k
ニュートン法の直感的な解釈
この辺りは▽の変化すなわ
ちヘッセ行列 HL(W)が小さ
いので大きく進む方が効率
がよい
 HL(W)-1：大
この辺りは▽の変化すな
わちヘッセ行列 HL(W)が
大きいので大きく進むと不
味い方向に行ってしまう。
 HL(W)-1 ：小
ニュートン法の問題点
 ニュートン法は勾配降下法より多くの場合で性
能がよいが、ヘッセ行列の逆行列を繰り返しの
度に計算しなければならない
 N×Nの行列の逆行列の計算にはO(N3)のコスト
がかかる。Nが大きくなると実用的でなくなる
 ヘッセ行列の逆行列を近似する行列を行列のか
け算だけによる更新式を使ってO(N2)で計算する
方法もある。
BFGS公式のヘッセ逆行列版（cf. 共立出版「最適化
法」p.122)
確率的勾配降下法
Stochastic Gradient Descent(SGD)
 ここまで述べてきた方法は全データを一挙に学習に
用いるバッチ処理
 1データないし少数のデータ毎に重みベクトルw学習
する方法：オンライン学習に近い
 最終結果としては、1ないし少数データ毎の学習で得られ
たwの平均
 メモリに全データを展開しなくてよい可能性もある省メ
モリしかし、全データを何回も繰り返し使うなら省メモリ
にならない 1つのデータは1回しか見ないストリームマイニング的
 2種類のSGD
 Sample Approximation(SA):1データ毎の学習
SGD(SA) と
w0
w1  w 0
バッチ学習
w k 
  lossw 0 on x1 , y1 
0 








loss w k  on x1 , y1 
w 2  w1
x1 , y1
w3  w 2
x2 , y2
loss w k  on x 2 , y2 
x3 , y 3
loss w k  on x3 , y3 
  1lossw1　on x 2 , y2 
  2 lossw 2 on x3 , y3 

:
w i  w i 1
  i 1lossw i 1　on xi , yi 

w m  w m1
 
lossw m1　on x m , ym 
 m1

1 m
w   wi
m i 1
x i, y i

loss w k  on xi , yi 

:
xm, ym
このデータ生成が確率的


loss w k  on x m , ym 
w
 k 1
w
k 
k  
1 m

    loss w k  on xi , yi  
 m i 1


さらに kを  1して上の処理を繰り返す

Sample Average Approximation(SAA)
SA inside SAA
全データからランダムにm個のデータをサン
プルしてm個のデータからなるデータ集合を
作る。
このようにして異なるデータ集合をk個作る。
データ集合(i)にSGD(SA)を適用して学習し、重
みベクトルw(i)を計算
m
1
最終結果 w   wi 
m
i 1
例：SGDによるサポートベクターマシン



1 m
T

min
1

y
w
xi


i

W
 m i 1
に注意すると SVDは以下のようになる

1 m
min  1  yi wT xi
W 2 B m
i 1

初期値： w 0  , 全データ数 : n
以下を k回繰り返す
｛
からランダムに生成
iを 1..n　if yi wT xi  1　then w  w  yi xi


if w 2  B then w  Bw w
w sum  w sum  w｝
結果： w  w sum k
2



 w 2

2

2

Download Report