[EECS 498-007 / 598-005] 4. Regularization + Optimization

김강태·2021년 1월 15일

EECS 498-007 / 598-005 Deep Learning for Computer Vision

( how do we find the best W? )

Optimization

w^* = argmin_wL(w)

# Assume X_te is [3073 x 10000], Y_te is [10000 x 1]
scores = Wbest.dot(Xte_cols)
# find the index with max score in each cloumn (the predicted class) 
Yte_predict = np.argmax(scores, axis = 0)
# and calculate accuracy (fraction of predictions that are correct)
np.mean(Yte_preddict == Yte)
# returne accuracy

\frac{df}{dx} = \lim_{h->0} \frac{f(x+h) - f(x)}{h}

Gradient Descent

w = initialize_weights()
for t in range(num_steps):
    dw = compute_gradient(loss_fn, data, w)
    w -= learning_rate * dw

method of initializing the weights()
: 이 weight를 초기화하는 방법은 다음 강의에서 좀더 적절하고 다양한 방법을 다루게 될 것이다.
num_of_steps()
: iteration 횟수이며 Gradient Descent에서 사용되는 다양한 stopping criteria가 있는데 강의 후반부에 다룬다.
learning_rate()
: 우리가 계산된 gradient를 얼마나 신뢰할 것 인가를 나타내며 이것은 얼마나 크게 움직일것인가를 결정하게 된다. 또한 우리의 알고리즘이 얼마나 빠르게 학습할 것인지를 결정한다.

Batch Gradient Descent

L(W) = \frac{1}{N}\sum^N_{i=1}L_i(x_i,y_i,W) + \lambda R(W) \\ \nabla_wL(W) = \frac{1}{N}\sum^N_{i=1}L_i(x_i,y_i,W) + \lambda \nabla_w R(W)

Stochastic Gradient Descent(SGD)

# Stochastic gradient descent
w = initialize_weights()
for t in range(num_steps):
	mini_batch = sample_data(data, batch_size)
	dw = compute_gradient(loss_fn, mini_batch, w)
    w -= learning_rate * dw

L(W) = \mathbb{E}_{(x,y)~_{p_{data}}} [L(x,y,W)] + \lambda R(W) \\ \approx \sum^N_{i=1}L(x_i, y_i, W) + \lambda R(W)

\nabla_w L(W) = \nabla_w \mathbb{E}_{(x,y)~_{p_{data}}} [L(x,y,W)] + \lambda \nabla_w R(W) \\ \approx \sum^N_{i=1} \nabla_w L(x_i, y_i, W) + \nabla_w R(W)

만약 아래의 loss의 contour plot(등고선) 처럼 (like taco shell) loss의 landscape가 한 방향으로는 빠르게 변하고 다른 방향으로는 천천히 변해간다면 어떻게 될까??
이때 gradient descent는 어떻게 움직일까?

Local Minima & Saddle point

SGD + Momentum

SGD \\ x_{t+1} = x_t - \alpha \nabla f(x_t)

for t range(num_steps):
	dw = compute_gradient(w)
  	w -= learning_rate * dw

SGD + Momentum\\ v_{t+1} = pv_t + \nabla f(x_t) \\ x_{t+1} = x_t - \alpha v_{t+1}

v = 0
for t in range(num_steps):
    dw = compute_gradietn(w)
    v = rho * v + dw
    w -= learning_rate * v

Nesterov Momentum

Nesterov Momentum\\ v_{t+1} = pv_t - \alpha \nabla f(x_t + pv_t) \\ x_{t+1} = x_t + v_{t+1}

v = 0 
for t in range(num_steps):
	old_v = v
    v = rho * v - learning_rate * compute_gradient(w)
    w -= rho * old_v - (1 + rho) * v

Adagrad

grad_squared = 0
for t in range(nun_steps) : 
    dw = compute_gradient(w)
    grad_squared += dw * dw
    w -= learning_rate * dw / (grad_squared.sqrt() + 1e-7)

RMSProp

grad_squared = 0
for t in range(nun_steps) : 
    dw = compute_gradient(w)
    grad_squared += decay_rate * grad_squared + (1 - decay_rate) * dw * dw
    w -= learning_rate * dw / (grad_squared.squr() + 1e-7)

Adam

moment1 = 0
moment2 = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    moment1 = beta1 * moment1 + (1 - beta1) * dw  # momentum
    moment2 = beta2 * moment2 + (1 - beta2) * dw * dw  # AdaGrad / RMSProp
    w -= learning_rate * moment1 / (moment2.sqrt() + 1e-7)
    
# beta1 & beta2 : each hyperparameter

moment1 = 0
moment2 = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    moment1 = beta1 * moment1 + (1 - beta1) * dw  # momentum
    moment2 = beta2 * moment2 + (1 - beta2) * dw * dw  # AdaGrad / RMSProp
    moment1_unbias = moment1 / (1 - beta1 ** t)
    moment2_unbias = moment2 / (1 - beta2 ** t)
    w -= learning_rate * moment1_unbias / (moment2_unbias.sqrt() + 1e-7)
    
# beta1 & beta2 : hyperparameter for each moment

Summery

이전에 보았던 regularization이 추가된 loss function을 가지고 weights를 update해나가는 optimization 방법론에 대해 살펴보며 기본적인 gradient descent의 동작 메커니즘에 대하여 살펴보았다.
Gradient algorithm 부터 시작하여 local minima, poor condition, saddle point 등 여러 발생할 수 있는 문제들을 새로운 optimization algorithm을 통해 극복해 나가는 모습을 살펴보았다.
다음 강의에서는 Neural Networks에 대한 기본적인 intro를 살펴보려한다.

개썅마이웨이로 shine my way

[EECS 498-007 / 598-005] 4. Regularization + Optimization

EECS 498-007 / 598-005 Deep Learning for Computer Vision

이번 포스팅은 제가 블로그에 hands-on ML 책의 gradient descent내용을 정리한 포스팅과 같이 보시면 좋습니다 ^^.

저번 강의에서 linear classifier의 score를 SVM loss, corss-entropy loss(softmax)를 사용한 loss 와 model의 overfitting을 방지하기위한 regularization을 더해주는 형태가 최종 L(W) 즉 loss function 이라는 것을 알아보았다.

그렇다면 linear classifier 와 loss function이 주어졌을때 우리는 어떻게 해당 loss를 만족하는 weights matrices 를 찾아갈 것인가?

Optimization

일반적인 의미로 loss function을 최소화 시키는 weights matrices W를 찾아가는 과정을 optimization이라고 한다.

* 이번 포스팅에서는 loss function을 단순히 weight matrix를 input으로 갖고 output으로 loss에대한 scalar value를 반환하는 abstract function으로서 볼것이다.

Optimization은 직관적으로 보면 우리가 크고 우거진 산의 계곡에서 눈을 가린채로 산 아래까지 찾아가는 과정으로 생각해볼 수 있다.

우리가 산에서 아래로 내려가는 방법은 단순하게 밑을 향해간다 라고 생각할 수 있지만 일반적으로 이러한 문제는 엄청 어렵다 그래서 실제로 우리는 다양한 iterative한 방법을 통하여 접근한다.

Idea1. Random search (bad idea!)

위 코드는 weight matrix에 해당하는 많은 random value를 만들어내고 각기 다른 matrix별 loss를 구한 후 lowest value를 찾아가는 과정을 반복하는 것이다.

또한 위 코드는 이전에 찾은 best W matrix와 test data를 dot prodoct 하여 나온 score 에서 가장 큰 (가장 좋은) 값들을 찾아 평균을 내주는 과정이다.

* 사실 이러한 코드는 성능이 매우 좋지 않다.

Idea2. Follow the slope

두번째로 살펴볼 방법은 local geometry 한 방법을 사용하는 것이다.

우리가 산 속에서 앞을 볼 수 없는 사람이라고 생각해 봤을때 산의 밑바닥이 어디인지 알 수 없지만, 주변을 돌아다니면서 얻은 정보를통해 어디가 밑으로 향하는 길인지 판단하고 진행하며 반복하여 밑으로 가는 방법이다.

In 1-dimension, the derivative of a function gives the slope

위의 수식은 매우 단순해 보이지만 꽤 잘 동작하는 알고리즘 수식이다.

singel scalar value를 input으로, single scalar value를 output으로 반환하는 형태로 어떤 x ( point ) 에서의 derivative 즉 slope(gradient)를 구하는 형태이다.

위 수식의 input x 를 scalar 가 아닌 vector로 바꿔 본다면 multiple demension으로 확장시켜 다변수 함수로 볼 수 있고 input vetor에 대하여 gradient의 집합인 vector 를 output으로 반환하는 형태가 된다.

위의 수식을 토대로 직접적으로 limit definition of the gradient를 구해보자.

gradient의 limit definition 과정을 numerical하게 실행해 보자.

이러한 방식으로 weight matrix W의 모든 dimension에 대해 반복하여 계산한다.

*calculate an analytic gradient

그래서 우리는 이전과같이 W의 모든 원소를 순회하는 것이 아니라 gradient를 구하는 식만 도출하고(dL/dW) gradient vector를 한번에 계산해버릴 수 있다.

* 실제로는 항상 위와같이 analytic gradient를 사용하지만 디버깅을 위해 numerical gradient를 사용하기도 한다. 이를 위해 아래와같이 pytorch 에서 함수로 제공되고 있다.

Gradient Descent

여태까지 보았듯이 loss fuction을 optimizing 하기위한 전략은 우리가 아무 point에서나 시작해도 local gradient direction을 알게되고 step을 반복하며 negative gradient로 진행을 하며 loss를 줄이는 것 이다.

이 핵심 개념을 간단한 코드를 통해 살펴보자

*이 algorithm에는 3가지의 hyperparameter가 있다.

위 그림은 gradient descent 알고리즘의 진행과정을 heatmap 으로 살펴본 것이다. 이 그림에서는 x 와 y 축에 두개의 weights에 대해서만 나타내었고, 각 color는 loss function의 크기를 나타낸다 (red region이 low loss를 나타냄).

initialized W가 그림의 하단에서 시작되어 loss function의 negative gradient를 매 step마다 찾아가며 진행함을 나타낸다.

이 그림이 나타내는 Gradient Descent algorithm의 특징은 곧장 bottom으로 가지 않는다는 것이다.

Batch Gradient Descent

첫번째 수식은 regularization이 추가된 loss function에 대한 일반적인 형태의 수식이며 이를 미분하여 나온 ∇wL(W)\nabla_wL(W)∇w​L(W)가 gradient vector를 구하는 식이다.

이 전에 보았던 gradient descent 방식은 data set의 크기가 매우 크다면 매 step에서 전체 training set에 대한 sum of loss를 구하기 때문에 매우 고비용이 되어 비효율적이다.

이러한 문제를 해결하기위한 변형 gradient descent algorithm이 있다.

Stochastic Gradient Descent(SGD)

SGD의 핵심은 loss fuction이 training data set에 대해 전부 계산하지 않고 mini-batch 라는 subsample을 만들어 대략적으로 계산한다. 보통 이러한 subsample의 size는 32, 64, 128을 사용한다고 한다.

코드를 통해 살펴보자

위 코드는 이전의 gradient descent 코드에서 추가로 매 스텝마다 full training data set를 batch size만큼 sampling 해주어 mini-batch의 gradient를 구하고 w를 update 해준다.

여기서 원래의 initialized weights, num of steps, learning rate에서 새로운 hyperparameter인 batch size가 추가되었다.

* batch size라는 하이퍼파라미터는 다른 하이퍼파라미터보다 모델이 덜 민감하게 반응한다고한다.

* 이 알고리즘의 본질적인 생각은 결정론적일 수도 있는 문제를 해결하기 위해 무작위성을 이용하는 것이다

이러한 방법에서 loss function을 생각해봤을때 full expectation의 근사치를 계산하기 위해서는 우리가 얼만큼의 sample을 취할지 결정 해야한다.

Problems with SGD

SGD algorithm에는 몇가지 문재가 발생 할 수있다.

만약 아래의 loss의 contour plot(등고선) 처럼 (like taco shell) loss의 landscape가 한 방향으로는 빠르게 변하고 다른 방향으로는 천천히 변해간다면 어떻게 될까??

이때 gradient descent는 어떻게 움직일까?

step size가 클 수록 아래 그림과 같이 step에 따른 matrix W 의 변화가 진동을하며(zigzag pattern을 보이며) 변화 할 수 있다.

이러한 문제에서 trade-off 가 존재한다.

SGD에서 step size를 크게 할 경우 위처럼 zigzag pattern을 보이고 이런 overshooting을 방지하기위해 step size를 작게할 경우 algorithm이 매우 느리게 수렴하게된다.

이 trade-off로 Loss function이 높은 condition number를 갖게된다.

* condition number란 입력값의 작은변화에대한 출력값의 변화의 정도를 측정하는 지표로 시스템이 민감한 정도를 정량적으로 보여주는 값을 뜻한다.

* 추가로 강의에선 이 경우엔 헤시안 행렬에서의 가장 큰 singular value와 가장 작은 singular value의 비율이 매우 높아진다고 한다.

Local Minima & Saddle point

SGD는 또한 local minimum와 saddle points문제가 나타날 수 있는 알고리즘이다.

local minima 는 zero gradient를 갖지만 사실 bottom of the function은 아닌 point 를 말한다. (global minimum point 가 아닌 local minimum point). algorithm이 step을 진행하다 이 local minimum을 만나 학습을 종료 시키는 경우 문제가되는 것이다.

아래의 그림처럼 어떤 방향으로는 loss가 증가하고 다른 방향으로는 감소하는 지점에서 gradient가 0가 되는 지점을 saddle point라고 한다.

saddle point보다 더 문제가 있는 monkey saddle형태가 아래와 같은 그림처럼 나타나는데 이는 saddle point뿐만 아니라 그 주변에서 평평한 형태를 지니기에 algorithm이 그 곳에서 안주 할 가능성이 높아지고 더디게 진행 될 수 있다.

SGD의 또 다른 문제로 SGD는 gradient를 계산할 때 small estimate of full data set만을 사용하기때문에 모든 step에서의 gradient가 bottom으로 향하는 올바른 direction과는 상관관계가 없어 아래의 그림에서 볼 수 있듯이 noisy하다는 것 이다.

이러한 여러 문제들을 해결하기위해 좀더 똑똑한 SGD version를 통해 개선된 Optimizer를 사용해야 한다.

SGD + Momentum

Momentum 의 핵심 idea는 weight를 업데이트 할 때 이 전에 계산한 gradient도 반영을 해주자는 것이다.

이전의 SGD를 다시 살펴보면 SGD에서는 모든 iteration동안 mini-batch sample에서 계산된 gradient를 통해 weight를 update시키는 방식이었다.

반면에 SGD + Momentum 에서는 이전의 움직인 방향을 뜻하는 velocity vector를 update에 적용시킨다.

이때의 velocity vector는 historical moving average of gradient를 뜻한다.

* 아래의 momentum 식이 통계학에서 EMA(Exponential Moving Average) 또는 EWMA(Exponential Weighted Moving Average)를 뜻한다고 한다.

이 전의 gradient도 계속 더해주기 때문에 속력이 아닌 속도(velocity)로 표현 되었고 이전 gradient를 얼마나 고려할 것인지를 뜻하는(friction or decay rate) 수식에서의 p, 코드에서의 rho 값은 일반적으로 0.9를 사용한다고 한다.

현재 위치에서의 gradient에 velocity를 더해주는 형태인 momentum update를 간단한 벡터로 표현하면 다음과 같다.

SGD + momentum은 기존 SGD의 세가지 문제점을 해결하면서 훨씬 빠르게 동작한다.

이러한 개념을 언덕에서 공을 굴리는 것으로 비유를 들면 공이 점점 내려가면서 속도가 붙어 local minimum 혹은 saddle point를 만나더라고 velocity를 통해 탈출할 수 있다는 개념이다.

이런 momentum 방식을 좀더 개선시킨 알고리즘이 있는데 이를 nesterov momentum이라 부른다.

Nesterov Momentum

nesterov momentum는 직전에 봤던 momentum과는 약간 다른 방식으로 update가 이루어진다.

위 그림처럼 기존의 momentum이 현재 point에서의 gradient와 이전 velocity를 더해주어 update를 하는 반면에 nesterov momentum은 현재의 point를 이전의 velocity 방향으로 움직인 후 옮겨진 point에서의 gradient를 구하여 update시켜주는 방식이다.

수식과 코드로 표현하면 아래와같다.

위 그림은 세가지 optimizer algorithm이 loss contour plot에서 이동하는 경로를 나타낸다.

그림에서 처럼 SGD+Momentum 과 Nesterov momentum은 bottom에서 overshoot 되는 경향을 보인다 (velocity를 사용했기 때문에). 이러한 momentum method들은 linear model 뿐만 아니라 많은 deep learning model 을 학습시킬때 흔하게 사용한다고한다.

첫번째 수식은 regularization이 추가된 loss function에 대한 일반적인 형태의 수식이며 이를 미분하여 나온 $\nabla_wL(W)$ 가 gradient vector를 구하는 식이다.

그림에서 처럼 SGD+Momentum 과 Nesterov momentum은 bottom에서 overshoot 되는 경향을 보인다 (velocity를 사용했기 때문에).
이러한 momentum method들은 linear model 뿐만 아니라 많은 deep learning model 을 학습시킬때 흔하게 사용한다고한다.

* 해당 내용의 자세한 내용은 링크의 논문에서 볼 수 있다
ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION

*
beta1 = 0.9
beta2 = 0.999
learning_rate = 1e-3 or 5e-4