[2.2.] Optimization Algorithms(1)

Mini-batch Gradient Descent

fast optimization algorithm

 

$$X = [x^{(1)}, x^{(2)}, x^{(3)}, \ldots, x^{(m)}]$$

$$Y = [y^{(1)}, y^{(2)}, y^{(3)}, \ldots, y^{(m)}]$$

- $X$는 $(n_{x}, m)$, $Y$는 $(1, m)$ 차원

 

$m$이 너무 크면 vectorization 해도 시간이 많이 걸림

gradient descent를 전체 훈련셋에 실시하는 것 = gradient descent 한 스텝 하기 전에 전체 훈련셋을 처리해야 함

전체 훈련셋을 모두 처리하기 전에 gradient descent를 시작하게 하면 더 빨라진다

 

training set을 baby training set으로 나누기로 함 = mini-batches

예를 들어 $m=5000000$일 때, 미니배치 $1000$로 세팅한다고 치자

 

$$X = [x^{(1)}, x^{(2)},\ldots, x^{(1000)}, | x^{(1001)}, x^{(1002)}, \ldots, x^{(2000)}, | x^{(2001)}, \ldots \ldots x^{(5000000)}]$$

미니배치 $X^{\{1\}}$, $X^{\{2\}}$, ..., $X^{\{5000\}}$

$$Y = [y^{(1)}, y^{(2)},\ldots, y^{(1000)}, | y^{(1001)}, y^{(1002)}, \ldots, y^{(2000)}, | y^{(2001)}, \ldots \ldots y^{(5000000)}]$$

미니배치 $Y^{\{1\}}$, $Y^{\{2\}}$, ..., $Y^{\{5000\}}$

--> $t$번째 미니배치 : $X^{\{t\}}$, $Y^{\{t\}}$

 

이때 $X$가 $(n_{x}, m)$이므로, $X^{\{t\}}$는 $(n_{x}, 1000)$, $Y^{\{t\}}$는 $(1, 1000)$

 

- Batch gradient descent : 전체 훈련셋을 통으로 하나의 batch로 보고, 모두 한꺼번에 한번에 처리

- Mini-batch gradient descent : $X^{\{t\}}$, $Y^{\{t\}}$를 한번에 처리

 

for $t=1,\ \ldots,\ 5000$

(1) Forward prop on $X^{\{t\}}$

- one step of gradient descent using $X^{\{t\}}$, $Y^{\{t\}}$

- 마치 $1000$개의 training sample 훈련하듯이 vectorization

$$Z^{[1]} = W^{[1]}X^{\{t\}} + b^{[1]}$$

$$A^{[1]} = g^{[1]}(Z^{[1]})$$

$$\ldots$$

$$A^{[L]} = g^{[L]}(Z^{[L]})$$

 

(2) cost function

- 하나의 미니배치에 대한 cost function

$$J^{\{t\}} = \frac{1}{1000}\sum_{i=1}^{l}L(\hat{y}^{(i)}, y^{(i)}) + \frac{\lambda}{1000}\sum \parallel {w^{[l]}} \parallel _F^{2}$$

- 여기서 $l$은 레이어가 아닌 미니배치 내 샘플 개수

- regularization

 

(3) back prop to compute gradients with respect to $J^{\{t\}}$ using $X^{\{t\}}$, $Y^{\{t\}}$

 

(4) update

$$w^{[l]} := w^{[l]} - \alpha dw^{[l]}$$

$$b^{[l]} :=b^{[l]} - \alpha db^{[l]}$$

 

*epoch : single pass through the training set

- batch gradient descent는 한 번의 epoch 동안 한 번의 gradient descent 계산

- mini-batch gradient descent는 한 번의 epoch 동안 5000번(미니배치 개수) gradient descent 계산

 

Understanding Mini-batch Gradient Descent

[training with mini-batch gradient descent]

- batch gradient descent

     - 한번의 iteration이라도 cost가 오르면 안 됨

 

- mini-batch gradient descent

     - 매 iteration마다 감소하지 않을 수도 있음

     - iteration마다 어떤 $X^{\{t\}}$, $Y^{\{t\}}$를 처리하므로 iteration마다 다른 학습셋을 훈련하는 듯한 효과 발생

 

 

mini-batch 사이즈도 선택해야 할 파라미터

- If mini-batch size == $m$ : batch gradient descent $(X^{\{t\}}, Y^{\{t\}})=(X,Y)$

- If mini-batch size == $1$ : stochastic gradient descent $(X^{\{t\}},Y^{\{t\}})=(x^{(i)},Y^{(i)})$ *각 샘플이 미니배치

 

cost function contour

stochastic gradient descent는 노이즈가 심함

stochastic gradient descent는 수렴하지 않고 minimu region을 오갈 것

따라서 실제 적용 시에 mini batch 사이즈는 $1~m$

 

- batch gradient descent (미니배치 사이즈 = m)

iteration마다 시간이 너무 걸림 물론 학습셋이 작을 경우엔 OK

 

- stochastic gradient descent (미니배치 사이즈 =1)

노이즈쯤이야 learning rate를 줄여 해결할 수 있는 문제지만, vectorization 통한 속도 개선을 모두 잃게 되므로 비효율적임

 

--> 따라서 1과 $m$ 사이 어딘가가 가장 빠른 학습 방법

     - vectorization이 가능

     - 기다릴 필요 없이 progress

 

[choosing your mini-batch size]

 

학습셋이 $2000$ 이하로 작다면 batch gradient descnet

그보다 크다면 일반적인 미니배치 사이즈 64, 129, 256, 512

 

make sure minibatches fit CPU/GPU memory

 

이 또한 반복적으로 시행하여 찾아야 할 하이퍼파라미터

 

Exponentially Weighted Averages

런던의 기온 트렌드를 알아보자 (기온들은 $\thata$로 표현하고 있음)

이때 사용할 수 있는 local average 혹은 moving average

 

처음 $V_{0} = 0$ 으로 initialize

$V_{1} = 0.9V_{0} + 0.1\theta_{1}$

$V_{2} = 0.9V_{1} + 0.1\theta_{2}$

$\ldots$

$V_{t} = 0.9V_{t-1} + 0.1\theta_{t}$

 

일반화 하자면 $V_{t} = \beta \cdot V_{t-1} + (1-\beta) \cdot \theta_{t}$, 이때 $\beta = 0.9$

$V_{t}$ as approximately averaging over $\approx \frac{1}{1-\beta}$ days' temperature

따라서 $\beta = 0.9$ 이면 지난 $10$일에 대한 평균, $\beta = 0.98$이면 지난 $50$일에 대한 평균, $\beta = 0.5$ 이면 지난 이틀 간 ...

--> $\beta$가 작아질수록 변화에 더 금방 adapt한다는 의미이므로 noisy해진다

 

$\beta$가 높아질수록 더 많은 날을 고려하므로 그래프가 스무드해진다 (larger window of temperatures)

 

 

Understanding Exponentially Weighted Averages

$v_{t} = \beta v_{t-1} + (1-\beta){\theta}_{t}$

$\beta$를 어떻게 설정하는지에 따라 ...

 

$$v_{100}=0.9v_{99}+0.1{\theta}_{100}$$

$$v_{99}=0.9v_{98}+0.1{\theta}_{99}$$

$$v_{98}=0.9v_{97}+0.1{\theta}_{98}$$

$$\ldots$$

 

위 식에서 $v_{100}$를 살펴보자면

 $v_{100}=0.1{\theta}_{100} + 0.9(0.1{\theta}_{99}+0.9(0.1{\theta}_{98} + \ldots))$

$= 0.1{\theta}_{100} + 0.1 \cdot 0.9 \cdot {\theta}_{99} +  0.1 \cdot {0.9}^{2} \cdot {\theta}_{98} + 0.1 \cdot {0.9}^{3} \cdot {\theta}_{97} + \ldots $

 

즉 $v_{100}$을 구하는 것은 temperature 그래프와 exponentially decaying function 그래프의 element-wise product를 구하여 합하는 것이다

 

$\theta$ 에 곱해지는 계수들은 ($0.1$,  $0.1 \cdot 0.9$, $0.1 \cdot {0.9}^{2}$, $0.1 \cdot {0.9}^{3}$, .... )

-> up to a detail called "bias correction"

 

How many days temperature is this averaging over?

$0.9^{10} \approx 0.35 \approx \frac{1}{e}$ (참고로, ${(1-\epsilon)}^{\frac{1}{\epsilon}} = \frac{1}{e}$)

즉, $10$일이 넘어가면 오늘값의 가중치의 $\frac{1}{3}$ 이하로 내려가므로 (weight decay) 10일이라고 볼 수 있음

$\beta$가 $0.98$로 좀더 커진다면? $0.98^{50} \approx \frac{1}{e}$ 이므로 50일이라고 볼 수 있음

일반화 하면 $\frac{1}{1-\beta}$일 이라고 할 수 있다

 

$v_{0} = 0$     # initialize

$v_{1} = \beta v_{0} + (1-\beta)\theta_{1}$

$v_{2} = \beta v_{1} + (1-\beta)\theta_{2}$

$v_{3} = \beta v_{2} + (1-\beta)\theta_{3}$

$\ldots$

 

일반화 하면

 

$$v_{\theta} = 0$$

$$Repeat\ \{$$

$$Get\ next\ \theta_{t}$$

$$v_{\theta}:=\beta v_{\theta} + (1-\beta) \theta_{t}$$

$$\}$$

 

장점: 메모리가 적게 든다 계속 overwrite 하면 됨

실제로 평균을 구한다고 최근 10일, 50일 간의 기온을 모두 더해서 나눈다면 더 정확하기는 하겠지만 메모리가 더 많이 든다