Deep-Learningの話 – Gradient descent optimization algorithms(1)

2018年2月1日実践コラム, 業界最新情報

optimizer

Deep Learningの話

Gradient descent optimization algorithms(1)

(この文章はこちらの論文[1]を基盤に作成したものでございます。)

＿勾配降下方（Gradient descent、GD）は NNを最適化する方法の中で最も一般的に使われている方法です。

これは NNのパラメーターを $\theta$ とした場合、NNからの結果値と実際値の差を定義する関数 $\nabla_\theta J(\theta)$ の値を最小化するため $\nabla_\theta J(\theta)$ をを用いる方法です。Gradient Descentでは $\theta$ に対し、勾配の反対方向にその勾配の大きさに比例する大きさほど移動することを繰返して最小化する $\theta$ を探します。一つのiterationでの変化式は次のようになります。

$\theta = \theta - \eta\nabla_\theta J(\theta)$

ここで $\eta$ は learning rateであり、最小値に至るためどのぐらいの大きさでiterationを更新したいのかを決定します。

最近のディープラーニングライブラリには GDを最適する色んなアルゴリズムを提供しています。（eg: KerasのOptimizer）しかし、それらの長所や短所についての概念がやや難しいため、実質的にどのようなものを使えば良いか困る時が個人的にも多かったので、今回は最適化関数について整理することになりました。

Gradient descent variants

Gradient descentは大きく三つに分類することができます。各々はどのぐらいのデータを用いて勾配の更新をするのかによって異なり、そのデータの量によってパラメーター更新の正確度と一つの更新に掛かる時間は trade-off 関係にあります。

Batch gradient descent

単純な gradient descentで、cost functionの勾配を計算時、全てのtraining datasetのパラメーター
$\theta$ に掛けての計算を行います。

$\theta = \theta - \eta\nabla_\theta J(\theta)$

言い換えると一つの更新を行うため、全てのデータセットに掛けての計算が必要となるため、batch gradient descentは遅くなるし、データセットによってはメモリの問題上扱いにくい時もあり得ります。計算時間は掛かりますが、batch gradient descentは convex surfacesの上 global minimumに、non-convex surface上の極小値に収束するのを保します。

alt text

Image 1: local minimum and global minimum on non-convex surface (参照)

Stochastic gradient descent

Stochastic gradient descent（SGD）はそれに反してパラメーターの更新を training データ $x^{(i)}$ とラベル $y^{(i)}$ ごとに行います。

$\theta = \theta - \eta\cdot\nabla_\theta J(\theta;x^{(i)};y^{(i)})$

Batch gradient descentは毎回のパラメーター更新をする前、同じ例に対する勾配を再計算し、データセットが大きくなるほど不必要な計算が増加することに反して、SGDは一回の更新でその不必要性な過程をせずに終わります。したがって速度も早くなります。

SGDは多くの変化に対し頻繁な更新を行うため、cost functionは激しく変動したりします。

Image 2: Fluctuations in the total objective function as gradient steps with respect to mini-batches are taken.(Wikipedia)

Batch gradient descentがパラメーターが置かれてあるconvexの最小値に収束することに反して、SGDは上の図のように変動するため、他のconvexに移動するポテンシャルを持っています。しかしながら、それが決してより良い極小値に至るわけではなく、その過程をもっと複雑にし逆に収束し難くする原因となったりもしますが、小さな学習率を設定することで overshootingする傾向を抑えれば batch gradient descentのように殆どの場合 global minimum（convex）や local minimum（non-convex）に収束します。

一般的に最適化する時、バイアスを生成しないようにするため、毎epochごとに training dataを shuffleする必要があります。
(参照)

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

Mini-batch gradient descent

Mini-batch gradient descentは二つの長所を取り、mini-batchごと n個の training examplesに対して更新を行います。

$\theta = \theta - \eta\cdot\nabla_\theta J(\theta;x^{(i+n)};y^{(i+n)})$

一つ一つのデータに対することより、mini-batchの平均値として更新するため、より安定的に収束する傾向を見せます。また、最近の deep learning ライブラリは効率的に計算をするように設計されており、通常の mini-batch sizesは 50 ~ 256ぐらいに設定をします（もちろん、場合によって異なる）。

for i in range(nb_epochs):
  np.random.shuffle(data)
  for batch in get_batches(data, batch_size=50):
    params_grad = evaluate_gradient(loss_function, batch, params)
    params = params - learning_rate * params_grad

Challenges

しかし、単純な mini-batch gradient descentだと良い収束そするとは言えない幾つかの問題点があります。

適合する learning rateを決めるのが難しい。小さな learning rate値はそれに相当する計算時間が掛かるし、高い learning rate値は収束を妨害し、cost functionの変動が引き起こされ時にはそれが発散する原因ともなります。
Learning rate schedulesは事前に定義されている scheduleにしたがって漸進的に learning rateを減らしますが、事前に定義される必要があり、データセットの特性を反映することが難しいです。
全てのパラメーターに対し同じ learning rateを採択する場合、例えばデータが sparseで、その特長が頻繁に異なるとしたら稀に起こる特徴を大きく反映してしまうため、繰り返される一般な特長と差を指定しないと行けないです。
NN上、普通に起こりうる non-convex 関数に対して最適化の過程の中それらの local minimaに陥らないようにするのもこそ難しい問題点であります。また Dauphin et al.[2]はこのような問題は local minimaに限らず saddle pointsにも収束してしまうことまで考えないと行けないのに問題があると言いました。そのような saddle pointsは多くの場合、同じ誤差を持つほぼ平面な時（全ての次元に対して勾配が０に近づいている場合）であります。