CS231n 3. Optimization: Stochastic Gradient Descent

CS231n

3. Optimization: Stochastic Gradient Descent

Optimization

loss function は判定の間違い(と重み行列の要素の大きさ)の計量で，学習(train)とはtrain setとそのlabelsを固定したまま$W$ を変化させてloss functionを最小化すること．その最も重要な技法がgradient descent(最急降下法).
loss function f を$W$ のみを変数とする関数と考えて，$\nabla f|_{W} = [\frac{\partial f}{\partial W_{1,1}} , ...]^T |_{W=W}$ をどうにかして計算し， $W - \eta \nabla f|_W$ を新たな$W$ にする．

Computing the gradient

$\nabla f|_{W}$を計算する方法は

1. 数値計算による方法
2. 解析的な方法 (back propagation) がある．解析的な方法は高速だが実装が難しいので，普段は解析的に微分係数を求めて，数値計算でそれが正しいかどうか確かめる(gradient check).

Computing the gradient numericaly with finite differences

$$\frac{\partial f(x_1, ..., x_n)}{\partial x_i} = lim_{h \rightarrow 0} \frac{f(x_1, ..., x_i + h, ...,x_n)}{h}$$ 計算機上では極限の計算ができないないので，hを十分小さな数として， $$\frac{f(x_1, ...,x_i + h,..., x_n) - f(x_1, ...,x_i, ...,x_n)}{h} = \frac{\partial f(x_1, ..., x_n)}{\partial x_i} + f_{x_i} (x_1, ...,x_n)h + o(h^3)$$ この計算の誤差は1次．一方 $$\frac{f(x_1, ..., x_i + h, ...,x_n) - f(x_1, ..., x_i - h, ...,x_n)}{2h} = \frac{\partial f(x_1, ..., x_n)}{\partial x_i} + \frac{1}{2} f_{x_i x_i}(x_1, ..., x_n)h^2+o(h^4)$$ 誤差は2次で，計算量はおよそ２倍になるが遥かに精度が高くなるので，ふつうはこちらの式で偏微分係数を計算する．

Computing the gradient analytically with Calculus

次章

Gradient Descent

vanilla Gradient Descent

loss functionが，全てのtrain setに対するものであるとき，すなわち

$$L = \frac{1}{|train|}\sum_{i \in train} L_i$$ の形をしている時，一回の$W$の更新に非常に時間がかかる場合がある．

Mini-batch Gradient Descent

train setを適当に分割してminibatchesをつくり，minibatchごとのloss function の勾配を計算して$W$ を更新していく.これをstochastic gradient descentと呼ぶこともある

Stochastic(online) Gradient Descent

train setのexample1つごとにloss function の勾配を計算して$W$ を更新していく方法．