경사하강법(Gradient Descent Algorithm)과 Optimizer 종류 정리 1️⃣

 

이번 포스팅에서는 경사하강법이 무엇인가에 대한 것과 Optimizer의 여러 종류들에 대해 알아보고자 한다.

목차는 대충 아래와 같다.

📌 Gradient Descent Algorithm이란?
📌 Batch gradient descent에 대해서
< 잠깐, 📌 SGD(Stochastic gradient descent)란? >
< local minimum과 이것을 피하기 위한 방법들 >
--- momentum 이용
1️⃣ Momentum
2️⃣ Nesterov Momentum
--- learning rate 이용
3️⃣ AdaGrad
4️⃣ RMSProp
5️⃣ Adam

 

 

📌 Gradient Descent Algorithm

먼저 경사하강 알고리즘이란 함수의 변화도가 가장 큰 방향으로 이동하고자 하는 알고리즘으로,

목적함수 J가 있을 때, 이 값을 최소화 하는 θ를 구하는 알고리즘이다.

( 여기서 θ는 learnable parameter이고, α는 stepsize로 hyper parameter이다. -> 늘 양수!)

 

Gradient descent는 one-step인 Normal Equation과 다르게 여러번 반복적인 갱신을 통해 최종적인 minimum에 도달하는 방식이다.

 

그리고, 전체 데이터셋에 대한 에러를 구한 뒤 기울기를 한번만 계산하여 모델의 parameter을 업데이트 한다.

헷갈릴수 있는게, 어떻게 전체 데이터에 대해 기울기를 한번만 구하지? 라는 생각을 가질 수 있으나

입력데이터 x에 대한 기울기를 계산하는 것이 아닌, 가중치 w에 대해 편미분을 하는것이기 때문에 x와 상관이 없다!

 

gradient descent 공식

 

이건 혹시 모를 기울기 유도 공식이다.

 

 

 

늘 양수인 α값에 θ가 반복적으로 갱신되며 최솟값에 도달하게 되는데, θ의 갱신은 기울기 하강(기울기가 음수)과 기울기 상승(기울기가 양수) 두가지로 나뉜다.

 

학습속도인 α값이 지나치게 작으면 최솟값까지 도달하는데 굉장히 많은 연산이 요구되고, 지나치게 크면 매우 큰 거리를 이동하여 오히려 최솟값으로부터 멀어질 수 있다. 따라서, 적절한 Learning Rate 설정이 필요하다.

 

기울기가 0인 극점에서 미분값은 0일 것이다.

그럼 바로 직전의 값과 갱신값 사이의 변화가 없게 된다.

바로 이 경우가 Cost Function이 최소가 되는 경우이므로 알고리즘은 갱신을 멈추게 된다.

 

 

지금 살펴본 이 경사하강 알고리즘은 Batch gradient descent(BGD)이다.

Batch는 Total training set이다.

즉, 갱신을 하는 매 단계마다 전체 training set을 활용하였기 때문에 이런 이름이 붙여졌다.

 

그러나 여기에 문제점이 존재한다.

일반적인 등고선 그래프에는 전체에서 가장 작은 값인 전역 최솟값(Global minimum)과 특정 구역 내에서 최솟값인 지역 최솟값(Local minimum)이 있는데,

초기 설정값에 따라 지역최소값에 빠져 최적의 θ를 찾지 못할 수도 있게 된다.

 

BUT

선형 회귀의 경우엔, Bowl-Shaped Function의 형태만을 가지기 때문에 Global minimum밖에 존재하지 않는다.

따라서, Linear Regression에서는 필연적으로 전역 최솟값으로 수렴된다.

 

 

 

장점

• 전체 업데이트가 한번에 이뤄져 계산 횟수가 적다.
• 전체 데이터에 대해 미분값을 계산하여 안정적으로 수렴한다.

단점

• 한번 갱신할 때 전체 데이터를 다뤄서 학습이 오래 걸린다.
• 갱신 직전까지 전체 데이터의 오차를 가지고 있어야 해 상대적으로 많은 메모리 요구됨
• Local Minimum 위험 + 빠져나오기 어려움

 

1️⃣ Momentum

 

이 Batch Gradient Descent의 단점인 Local Minimum을 해결하기 위해 도입된 것이 있다. (+ 학습 느린것도)

SGD(Stochastic gradient descent)의 단점인 느린 학습 속도, saddle point에서의 학습 종료, 심한 진동 문제 또한 해결 가능하다.

바로, Momentum!!

: 과거에 이동했던 방식을 기억하는 것으로, 관성을 같이 고려하여 변수가 가던 방향으로 계속 가도록하는 속도(velocity)항을 추가하는 것.

 

올바른 방향으로 가고 있다면 점점 더 속도가 붙어 학습이 더 빨라질 것이고, 기울기가 0인 안장점(saddle point)이더라도 속도가 존재하므로 계속 이동해 안장점을 잘 탈출할 수 있게 한다. (SGD Momentum이라고도 한다.)

 

그래서, saddle point를 만나거나 local minimum에 빠져도 그 지점을 벗어날 수 있다.

 

 

 

 

 

아무튼 이 momentum 알고리즘은 특히 SGD가 Oscilation 현상(진동)을 겪을 때 큰 빛을 발한다.

 

➡️ SGD가 saddle point에 걸려도 이동하던 방향에 관성이 걸리게 되어 진동을 하게 되더라도 중앙에 가는 방향으로 힘을 얻기 때문에 SGD에 비해 상대적으로 빠르게 이동!!

 

💡 잠깐, SGD?

: 하나의 iteration 안에서 입력 데이터 한개만을 사용하여 그 데이터에 대해 error를 계산하고 gradient descent 알고리즘을 적용하는 방법. (무작위화)
즉, 데이터셋에 100개의 샘플이 있다면 100번의 업데이트가 진행된다.
(BGD는 100개의 샘플이 있으면 100*100번의 업데이트가 진행됨->하나의 iteration에서 100번 update하므로)

 

• 빠른 속도로 수렴한다.
• local minimum에 빠질 위험이 적다.
• but 데이터셋이 매우 크면 매번 연산하는것에 메모리 사용량이 늘어난다.

 

Mini-batch gradient descent(MSGD)

: SGD와는 다른 알고리즘이긴 하나, 요즘엔 많이들 혼용해서 부른다고 한다.

한개만 사용하는 SGD와 다르게, batch-size를 지정해주면 그 크기에 맞춰서 SGD처럼 작동한다.

즉, 데이터셋에 100개의 샘플이 있고 batch-size가 5라면, 20개의 batch를 가지기 때문에 20번의 업데이트가 진행된다.

 

• SGD에 비해 메모리 사용이 절약된다.
• SGD에 비해 local optima에 빠질 위험이 줄어든다.
• batch를 나누기 때문에 병렬 처리에 유리하다.

 

BGD(batch gradient descent), SGD, MGD를 한눈에 보면 아래 그림과 같다.

https://bruders.tistory.com/91

 

 

 

momentum에 대해 간략히 알아봤다.

BUT 이것에도 단점이 존재했으니..

바로 Overshooting 문제점이 있다.

➡️ 경사가 가파른 곳을 빠른 속도로 내려오다 관성을 이기지 못하고 minimum 지점을 지나쳐버리는 현상이다.

gradient가 속도보다 작아서 실제 step이 커지게 되어 지나치게 된다.

 

그림으로 함께 이해해 보자.

 

 

 

이 overshooting 문제점을 개선한 알고리즘이 바로 다음에 소개할 Nesterov Momentum (NAG)이다.

 

 

 

2️⃣  Nesterov momentum (NAG)

: Momentum 방식 기반이지만 gradient 계산방법이 조금 다르다.

현재의 속도 벡터와 현재 속도로 한걸음 미리 가 본 위치의 그래디언트 벡터를 더해 다음 위치를 정한다.

 

즉, 다음속도 vt+1는​ 현재 속도에 마찰 계수 ρ를 곱한 뒤 한걸음 미리 가 본 위치의 그래디언트를 빼서 계산한다.

 

 

 

 

 

그럼 Nesterov Momentum이 어떤 부분에서 overshooting이 억제되는지 변수 치환 유도 과정을 풀어보면서 알아보자!

 

 

정리하자면,

 

Momentum

• 실제 스텝(actual step) = momentum + 기울기 값
• 속도는 빠르지만 관성에 의해 멈춰야 할 시점에도 더 멀리가는 단점 (overshooting)

Nesterov Momentum

• 모멘텀 값이 적용된 지점에서 기울기 값 계산
• 모멘텀으로 절반 정도 이동 후 어떤 방식으로 이동할지 다시 계산하여 스템 결정 (overshooting 개선)

---

 

지금까지는 momentum 알고리즘을 이용한 방법들을 알아보았다.

이번엔 learning rate를 조절하는 방식을 이용한 방법들에 대해서 알아보자.

 

3️⃣  AdaGrad

: 각 방향으로의 learning rate를 적응적으로 조율해서 학습효율을 높이는 방법이다.

즉, 많이 변화한 변수는 최적해에 근접했을 거란 가정하에 작은 크기로 이동하면서 값을 세밀하게 조정하고,

반대로 적게 변화한 변수는 학습률을 크게 하여 빠르게 오차 값을 줄이고자 하는 방식이다.

 

"각각의 매개변수"에 적응적으로(Adaptive) 맞춤형 값을 만들어주는거다.

 

그럼, 어떻게 Adaptive한 값을 만들어주는걸까?

바로 곡면의 변화량을 체크해주면 된다! 

곡면의 변화량은 기울기벡터의 제곱합으로 볼 수 있다.

 

 

AdaGrad의 진행 방향

 

 

BUT..

AdaGrad에도 단점이 존재했으니..

 

바로  Gradient^2 값을 이용하기 때문에, gradient의 누적값으로 인해 Learning rate값이 아주 작아질 수 있다는 것이다.

예를 들어, gradient값이 아주 많이 누적되어 r값이 많이 커져 learning rate인 α값이 지나치게 작아지면 그 지점에서 더이상 학습이 일어나지 않게 된다..!!

 

이 단점을 해결하기 위해..ㅎㅎ

RMSProp가 등장하였다.

 

하나의 알고리즘의 단점을 계속해서 업데이트하는 방식으로 진화해가고있다.

발전되는 스토리를 쭉 보다보면 경이롭고 신기하고 너무 재밌다ㅎㅎ

 

참고한 블로그의 필자가 Adam만 알면되지 이전것들은 뭣하러 알아야 하냐는 소리를 들었다고 했다.

글쎄, 이런 역사들을 쭉 훑어보면서 어떤 단점들을 발견했고 이를 어떤 방식으로 발전시켜나갔는지를 아는 것은

결국 ML Developer의 로드맵의 방향이 아닐까싶다.

(약간 한국사 공부하는 기분ㅎ)

 

아무튼 다시 돌아와서 현재 아주 잘쓰이는 Adam은 이 RMSProp을 발전시킨 방법이다.

그럼 RMSProp과 Adam은 다음 포스팅에서 계속해서 알아보겠다!!

 

 

[참고]

https://box-world.tistory.com/7

https://velog.io/@cha-suyeon/DL-%EC%B5%9C%EC%A0%81%ED%99%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98