CS182 - [Lecture 4] Optimization

Part 1

Gradient Descent

해당 챕터에서는 loss를 감소시키는 데 사용되는 optimization에 대해 알아본다.

먼저 2장에서 언급했던 opitimization인 gradient descent에 대해 복습해보자.

 

$ -\sum_{i}^{} logp_{\Theta}(y_{i}|x_{i}) $로 정의되는 loss function을 생각해보자.

파라미터가 2D라고 한다면 각 파라미터에 대한 loss를 우측 하단의 그래프처럼 시각화할 수 있다.

 

Gradient descent는 loss를 감소시키기 위해 두 단계를 거친다.

1. Loss를 감소시키는 방향 v를 찾는다.

2. 해당 방향에 small constant인 $ \alpha $를 곱하여 파라미터에 더함으로써 파라미터를 업데이트한다..

이때 $ \alpha $는 learning rate라고 불리며, 너무 크거나 작지 않도록 설정해야 한다.

 

그렇다면 loss를 감소시키는 방향인 v는 어떻게 구할까?

좌측의 그래프를 보면 loss function에서 해당 loss 값에 대해 미분한 값을 -1 곱해준 값이 v가 된다.

즉, 기울기가 음수라면 v는 양수가 될 것이고, 기울기가 양수라면 v는 음수가 될 것이다.

만약 파라미터가 여러 개라면 각각의 파라미터에 대해 loss function을 미분함으로써 v를 구해준다.

이때 v를 gradient라고 부른다. 

 

 

Gradient descent를 시각화하면 다음과 같다.

같은 contour(등치선)에 있는 점은 같은 loss값(\(L(\Theta)\))을 갖는다.

 

그림에서 확인할 수 있듯, gradient descent는 파라미터에 gradient 값을 빼가면서 다른 contour로 이동하고,

최종적으로 optimum(loss의 최솟값)을 향해 나아가는 것을 목표로 한다.

 

 

하지만 gradient descent의 문제점은 optimum으로 이동하는 것이 보장되지 않는다는 점이다.

위의 그림에서 확인할 수 있듯, loss가 optimum에 도착하지 못하고 solution 부분에서 멈추고 있다.

즉, gradient descent를 활용하여 가장 가파른 방향으로 가는 것이 항상 최선의 방법은 아니라는 것이다.

 

 

이러한 단점을 가진 gradient descent를 좋은 optimizer라고 할 수 있을까?

 

Chapter 2에서 배웠던 logistic regression에서는 꽤 좋은 것으로 보인다.

Loss function이 negative likelihood로 정의된 logistic regression의 경우,

해당 loss function은 convex가 보장된다.

 

Convex란 중앙의 첫 번째 그래프와 같이, 그래프의 어느 두 점을 연결해도 항상 그래프 위에 있는 그래프를 의미한다.

Convex functions의 경우 gradient descent 같은 간단한 알고리즘에서 보통 좋은 성능을 보인다.

즉, gradient descent를 통해 global optimum을 찾을 수 있는 경우가 많다.

 

 

하지만 모델이 복잡해질수록 loss function이 non-convex function일 확률이 증가하기 때문에,

실제로 활용되는 모델의 대부분의 loss function은 non-convex function에 해당한다.

Non-convex functions은 시각화조차 쉽지 않으며,

Neural networks처럼 파라미터의 개수가 많을수록 loss function의 형태가 더욱 복잡해진다.

 

하단의 좌측 그림은 neural network 모델인 Resnet의 ImageNet에 대한 loss function을 시각화한 것으로,

Convex functions에서 볼 수 없는 다양한 형태적 특징들을 확인할 수 있다.

 

Non-convex functions에서 나타날 수 있는 형태적 특징들 중 가장 대표적인 세 가지는

Local optimum, Plateau, Saddle point가 있다.

 

가장 먼저 Local optimum에 대해 알아보자.

 

 

아마 위의 세 가지 특징들 중 가장 익숙한 것이 local optima일 것이다.

그만큼 자주 논의되는 중요한 특징이라 할 수 있다.

 

Local optima는 loss가 최소가 아님에도 마치 global optima처럼 해당 지점의 미분 값(기울기)이 0인 지점이다.

따라서 gradient descent 관점에서 파라미터를 개선할 방향이 존재하지 않는다.

더 큰 문제점은 우리는 파라미터를 개선할 방향이 없는 지점이 local optima인지 global optima인지 알 수 없다는 것이다.

따라서 모델의 loss가 최소가 되지 않았음에도 학습할 방향이 존재하지 않아, 모델의 성능 개선이 저해된다.

 

하지만 놀랍게도 파라미터의 개수가 증가할수록 local optima 문제점이 완화된다고 한다.

파라미터의 개수가 많은 big networks에서는 local optima가 당연히 존재하긴 하지만,

하단의 히스토그램처럼 globla optima와 비교했을 때 큰 차이가 나지 않는다.

또한 local optima의 분포가 밀집되어있기 때문에 생각만큼 큰 문제점은 아니라고 한다.

 

 

Plateaus는 gradient가 굉장히 작은 부분이 넓게 분포된 영역을 말한다.

만약 learning rates를 작게 설정하면 palteaus를 빠져나올 수 없기 때문에 충분한 크기로 설정해야 한다.

 

 

Saddle point는 gradient가 0이면서(혹은 0에 매우 가까우면서) 축에 따라 최솟값 혹은 최댓값을 가지는 영역이다.

파라미터가 여러 개일 때 형성될 수 있는 영역으로, neural networks에서 흔히 생겨난다고 한다.

 

 

Loss functions에서 각 파라미터에 대해 local minimum이나 maximum을 가지는 부분은 critical point에 해당한다.

Critical point에서는 기울기가 0이기 때문에,

여러 파라미터의 최솟값과 최댓값으로 이루어진 saddlie point를 빠져나오기란 쉽지 않다.

 

Saddle point에서 각 파라미터가 최솟값을 가지는지 혹은 최댓값을 가지는지는 Hessian matrix를 통해 판단한다.

Hessian matrix는 loss functions를 두 개의 파라미터(같은 파라미터인 경우도 가능)에 대해 두 번 미분한 값들을 가지고 있다.

Hessian matrix의 모든 diagonal entries가 양수라면 minimum을, 음수라면 maximum을 의미한다.

 

파라미터가 고차원 일 때는 saddle point로 인해 발생하는 문제가 빈번하기 때문에 

Saddle point를 빠져나오기 위한 optimzer가 요구된다.

 

 

Part 2

Improvement directions

 

지금까지 살펴본 내용에 따르면 gradient descent가 가지는 한계가 명확해 보인다.

Global minimum이 아님에도 gradient가 0이 되는 지점이 존재함으로써 발생하는 문제점들을 해결하기 위해서는 어떻게 해야 할까?

 

Global minimum에 대한 올바른 방향을 찾고, 즉 최적의 방향을 찾고, 그 방향으로 모델이 학습하도록 유도하면 될 것이다.

그렇다면 최적의 방향은 어떻게 찾을 수 있을까?

 

Newton's method는 gradient descent보다 복잡한 알고리즘으로, 보다 훌륭한 방향을 제시한다.

(Loss functions의 모든 형태적 문제점들을 해결하지는 못한다고 한다.)

Newton's method는 Taylor series에서 아이디어를 얻은 optimization 알고리즘이다.

 

 

하지만 Newthon's method는 실제 neural network의 optimization 알고리즘으로 활용되지 않는다.

Newthon's method를 사용하기 위해서는 Hessian matrix를 사용해야 하는데,

이를 계산하는 과정에서 \(O(n^{2})\)의 시간이 소요되고, 최종적으로 \(O(n^{3})\)이 소요되기 때문이다.

Gradient descent의 실행시간이 대략 \(O(n)\)이라는 점과

neural network의 파라미터 개수가 많다는 것을 감안하면 실제로 실행시키기 어려운 실행 속도임은 자명하다.

 

 

우리는 알고리즘의 성능뿐만 아니라 실행 속도 또한 고려해야 한다.

Optimizer의 성능 개선과 실행 속도 측면에서, momentum은 효과적인 알고리즘이라 할 수 있다.

 

위 그림의 빨간색 선들을 보면, 전반적으로 global minimum으로 나아가려는 경향을 가지지만,

완벽하게 올바른 방향으로 나아가지는 않는다.

따라서 gradient descent에서의 '일반적으로 globla minimum으로 나아가려는 경향'을 고려했을 때,

적절한 gradient steps들에 대해 평균을 구하여 이를 모델의 개선 방향에 추가해준다면

최적의 방향에 가까운 방향성을 가지게 될 것이다.

 

만약 다음 gradient step에서 잘못된(혹은 이전과 다른) 방향으로 나아가려 하면 그 방향으로 나아가려는 효과를 감소시키고,

같은 방향으로 나아가려 한다면 step의 정도를 증가시키는 효과를 갖는다.

즉, momentum은 불필요한 방향으로 나아가는 것을 방지해주고 global minimum에 빠르게 접근하도록 해준다.

 

 

Momentum은 learning rate에 곱해지는 loss function에서의 gradient에 값에

이전 방향의 정보를 포함하고 있는 값을 더함으로써 이루어진다.

Newton's method의 일부 이점을 가져오면서도

실행 속도나 메모리 측면에서 추가적으로 발생하는 비용이 거의 없다는 장점이 있다.

 

 

다음으로 gradient scale에 대해 알아보자.

우리는 loss function을 각 파라미터에 대해 미분한 값을 통해 '어느 방향'으로 나아가야 할지를 파악할 수 있었다.

그렇다면 그 방향으로 얼마큼 나아가야 할까?

 

먼저 loss function에 대해 살펴보면, optimum과 loss 값의 차이가 클수록 gradient의 값이 커지고,

optimum에 가까워질수록 gradient가 작아짐을 알 수 있다.

Gradient가 지나치게 클 경우 over shooting으로 인해 step을 지날 때마다 loss가 오히려 커질 것이고,

Gradient가 지나치게 작아 파라미터의 업데이트가 미미할 경우 모델의 성능 개선은 이루어지지 않을 것이다.

따라서 gradient의 크기를 적절한 범위 내에서 조절할 수 있는 방법이 필요하며,

주로 gradient에 곱해지는 learning rate의 크기를 조절함으로써 이루어진다.

 

 

학습 step에 따라 learning rate를 조절함으로써 gradient scale을 조절하는 알고리즘들에 대해 알아보자.

AdaGrad는 지금까지 많이 업데이트된 변수는 적게, 적게 업데이트된 변수는 많이 업데이트하는 알고리즘이다.

 

\(s_{k}\)는 k번째 step에서 파라미터가 업데이트된 총량을 의미하며,

k-1번째까지의 gradient들의 제곱을 더한 값들로 구성된다.

\(s_{k}\)는 파라미터의 업데이트에서 루트가 씌워진 채 분모에 들어감으로써  파라미터의 업데이트를 조절하게 된다.

만약 지금까지의 업데이트된 총량이 커지면 분모가 커져 업데이트의 양은 감소하게 될 것이며,

업데이트된 총량이 작다면 파라미터의 업데이트가 큰 폭으로 이루어질 것이다.

 

하지만 \(s_{k}\)는 결국 step이 증가함에 따라 증가하기 때문에

결국에는 learning rate가 지속적으로 감소하게 되는 단점이 있다.

 

 

RMSProp는 Adagrad의 단점을 개선한 알고리즘이다.

RMSProp의 \(s_{k}\)는 Adagrad와 다르게 '최근에' 업데이트 한 정도를 고려한다.

\(s_{k-1}\)과 gradient의 제곱에 상수를 곱해줌으로써 최근의 정도를 조절한다.

 

 

Adam은 RMSProp과 Momentum의 장점을 지닌, 자주 언급되는 optimizer이다.

\(m_{k}\)는 momentum의 의미를 지니는 변수로, gradient와 이전의 momentum 값에 의해 업데이트된다.

\(v_{k}\)는 RMSPorp의 의미를 가지는 변수로, gradient의 제곱과 이전의 값에 의해 업데이트된다.

 

추가적으로 행해지는 계산은 Bias correction으로, 

초기 구간의 Exponentially weighted averages(지수 가중 평균)에서 발생하는 문제를 해결하기 위함이다.

초기의 \(m_{k}\)와 \(v_{k}\)의 값이 매우 작기 때문에, 해당 계산을 통해 크기를 보정해준다.

Step이 증가할 수록 \(B^{k}\)의 크기가 증가하기 때문에 해당 계산이 가지는 의미는 감소하게 된다.

 

(Exponentially weighted averages란 이전의 데이터들을 축적한 데이터에서

오래된 데이터가 미치는 영향을 지수적으로 감쇠하도록 만들어주는 방법으로, 

\(m_{k}\)와 \(v_{k}\)의 값을 구할 때 사용된다.)

 

+ Optimizer Algorithms 및 Exponentially weighted averages 참고자료

https://velog.io/@minjung-s/Optimization-Algorithm

 

 

Part 3

Stochastic Optimization

 

지금까지 gradient descent과 관련된 optimizer에 대해 알아보았다.

Gradient descent가 가지는 문제점을 해결하면서 시간 복잡도를 고려한 알고리즘들이 핵심이었다.

하지만 여전히 gradient descent를 사용하기에는 문제가 있다.

 

Gradient descent에서 사용되는 loss function의 경우 모든 데이터에 대한 계산이 발생한다.

딥러닝에서 자주 활용되는 데이터셋인 ImageNet의 경우 이미지가 1.5 million개가 존재하기 때문에,

한 번의 step에서 모든 이미지에 대한 계산을 시행하는 것은 매우 오랜 시간이 소요될 것이며,

이렇듯 전체 trainset을 한 번의 step에서 모두 사용하는 것을 batch gradient descent라 한다.

 

이와 대조적으로 각 step에서 일부 데이터(mini-batch)를 추출하여 학습하는 방법을

Stochastic gradient descent라고 한다.

 

 

Stochastic gradient descent에서는 각 step마다 데이터셋에서 하나의 batch를 선택하여 학습한다.

(Batch의 크기는 보통 32, 64이며, 전체 데이터셋과 비교했을 때 매우 작다.)

한 번의 학습에 전체 데이터가 아닌 일부 데이터만 사용하기 때문에 batch gradient descent보다

다소 부정확할 가능성이 존재하지만, 계산 속도가 훨씬 빠를뿐더러

학습을 여러 번 반복할수록 batch gradient descent의 결과에 수렴하게 된다.

또한 local minimum에 빠지지 않고 더 좋은 방향으로 수렴할 가능성 또한 존재한다.

 

하지만 실제로 stochastic graident descent를 사용할 때는

각 step마다 랜덤 한 데이터를 선택하지는 않는다.

많은 이미지에 대해 각 step마다 랜덤한 데이터를 선택하는 것은

많은 메모리 접근을 유발하므로 오랜 시간이 걸릴 수 있다.

 

따라서 실제로 사용할 때는 학습 이전에 데이터셋을 미리 한 번 섞고 배치를 구성하는 방식을 사용한다.

이후에 학습되는 mini batch의 순서가 같으므로 정확한 방법은 아니지만 계산 측면에서 매우 효율적이다.

 

 

위 그래프는 learning rate에 따라 epoch에 따른 loss값의 수렴이 어떠한 양상을 갖는지 보여준다.

 

빨간색 그래프는 epoch가 증가함에 따라 (학습이 진행됨에 따라) loss가 낮아지므로

적절한 learning rate를 가졌다고 말할 수 있다.

 

초록색 그래프는 loss가 감소하는 속도가 낮을뿐더러 epoch의 크기가 충분히 클 때

loss가 큰 값을 가진채 개선되지 않는 모습을 보여준다.

이는 learning rate가 작기 때문이며, 우측 상단의 그래프에서 볼 수 있듯이

Plateau와 같은 영역에 갇힐 수 있기 때문이다.

 

노란색 그래프는 loss가 초반에 급격히 감소한 이후 loss가 큰 값을 유지한 채 개선되지 않고 있다.

이는 learning rate가 크기 때문에 초반에는 optimum 방향으로 빠른 접근이 가능하지만

Optimum 근처에서는 over shooting이 발생하여 optimum에 더 이상 접근하지 못하기 때문이다.

 

이 정보들을 종합해보면, learning rate는 초반에 큰 값을 가졌다가

이후에 갈수록 작은 값을 가진다면 빠른 속도로 optimum에 접근할 수 있을 것이다.

 

위 그래프는 AlexNet을 ImageNet으로 학습한 것이며, 

초기에 learning rate를 큰 값으로 설정한 후 특정 epoch에서 learning rate를 감소시켰을 때

Training accuracy와 validaiton accuracy에서 좋은 성능을 보였음을 알 수 있다.

 

이러한 방법을 learning rate decay schedules라고 하며,

SGD + Momentum optimizer에서 효과적인 성능을 발휘한다.

 

SGD + Momentum과 ADAM의 성능에 대해 많은 의견이 존재하지만,

정확도 측면에서는 전자가, tuning에 따른 성능 개선 측면에서는 후자가 유리하다고 한다.

 

 

그렇다면 하이퍼 파라미터의 튜닝은 어떠한 방식으로 진행될까?

Stochastic gradient descent의 대표적인 하이퍼 파라미터로는

Batch size, learning rate, momentum이 있다.

 

Batch size의 경우 크기가 클수록 optimum에 안전하게 수렴한다는 장점이 있지만,

크기가 클 수록 계산 비용이 크다는 단점이 있다.

따라서 batch size를 설정할 경우에는 계산에 사용되는 메모리의 크기를 고려해야 할 것이다.

 

Learning rate는 이전에 언급했던 바와 같이 초반에 크게 설정하여 빠르게 근접하도록 한 후,

Over shooting을 피하기 위해 시간이 지남에 따라 감소하도록 하는 것이 좋다.

Momentum은 보통 default 값을 사용하며, tuning에 따른 성능 차이가 크지 않다고 한다.

 

Stochastic gradient descent와 Regluarization의 관계는 매우 복잡하다고 한다.

일부는 SGD를 Regularization의 일종으로 보고 validation loss에서 tuning 해야 한다고 주장하며,

일부는 optimization의 파라미터 이기 때문에 training loss에서 tuning 해야 한다고 주장한다. (3장에서 언급)

 

---

References

• https://www.youtube.com/watch?v=RdoZWcXmXhk&list=PL_iWQOsE6TfVmKkQHucjPAoRtIJYt8a5A&index=11
• https://cs182sp21.github.io/