[Deep Learning] Basic Algorithms for Gradient-based Optimization

본 포스팅은 

Ian Goodfellow et.al 의 Deep learning 교재와 

카이스트 산업 및 시스템 공학과 박찬영 교수님의 강의를 참고하여 제작되었음을 밝힙니다. 

 

그 외 다양한 블로그 글들을 참고하였습니다. 

 

Reference, 

[1] Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep learning. MIT press. 

Chapter 8, Optimization for Training Deep Model

https://www.deeplearningbook.org/

[2] 카이스트 산업 및 시스템 공학부 박찬영, "지식 서비스를 위한 기계학습" 강의 자료

[3] Onds 님의 블로그, https://ardino.tistory.com

[4] Beumsu Kim's Blog, https://shuuki4.github.io/deep%20learning/2016/05/20/Gradient-Descent-Algorithm-Overview.html

[5] https://deepestdocs.readthedocs.io/en/latest/002_deep_learning_part_1/0021/#momentum

[6] 산업수학혁신센터, https://icim.nims.re.kr/post/easyMath/428

 

Gradient Descent (이하 GD) 는 신경망을 학습할 때 기본적으로 사용되는 가중치 업데이트 방법입니다. 구체적으로는 디자인된 loss function을 minimize할 있는 optima를 찾는 과정이고 closed form의 행렬 연산이 매우 오래 걸리기 때문에 iterative한 방법으로 점점 optima한 곳으로 수렴하게 하는 방법을 의미합니다. 

그러면 입력 데이터 전체에 대해서 gradient를 수행하게 될 때, 우리는 이것을 Batch Gradient Descent라고 부릅니다. 하지만 일반적으로 전체 데이터를 한번에 input으로 받아 GD를 수행하는 경우는 드뭅니다. 수천만개에서 수억개에 이르는 input이 들어올 때, Computational cost가 매우 크기 때문입니다. 훈련 시간도 오래걸리지만 Out of memory도 발생할 가능성이 높기 때문입니다. 그래서 일반적으로는 전체 데이터를 다 쓰지 않고 일정량의 데이터를 나누어 ( mini-batch ) 그 배치 별로 GD를 수행하게 됩니다. 물론 전체 데이터를 사용하는 것에 비해 variance가 더 클 수 밖에 없고 정확도가 떨어지지만 훨씬 계산 속도가 빠르기 때문에, 같은 시간에 더 많은 step을 반복할 수 있기 때문에 많은 epoch를 수행하게 되면 Batch GD와 유사한 결과를 가지게 됩니다. 이 방법을 바로 Stochastic Gradient Descent (이하 SGD)라고 합니다.

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

물론 이 batch를 나누어서 한다는 점이 여러 리스크를 낳기 때문에 이를 극복하고자 하는 많은 방법이 도입되어 왔습니다. 본 장에서 메인 화두는 아니기 때문에 다루지는 않지만, 예를 들어 batch를 나누었을 때, 그 배치 간의 distribution에 차이가 생기는 Internal Covariate Shift 문제가 대표적인 예입니다. 이 문제를 극복하기 위해 도입된 방법이 바로 그 유명한 Batch-Normalization입니다. 이 방법에 대해서는 추후에 기회가 되면 자세하게 다루도록 하겠습니다. 혹시 관심이 있으신 분들은 본 방법이 도입된 논문과 잘 정리된 포스팅을 추가로 링크를 공유합니다.

 

About Batch Normalization Reference,

Ioffe, S., & Szegedy, C. (2015, June). Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning (pp. 448-456). PMLR.

http://proceedings.mlr.press/v37/ioffe15.html

Kim Jinsol님의 블로그 https://gaussian37.github.io/dl-concept-batchnorm/

문과생도 이해하는 딥러닝 https://sacko.tistory.com/44

 

다시 본론으로 돌아와서 이러한 SGD를 사용하게 될 때 여러가지 문제를 마주하게 됩니다. 가장 큰 문제점 중 하나는 모델이 수렴하는 속도가 매우 느리다는 것입니다. 아래 그림을 살펴보겠습니다.

출처 : https://shuuki4.github.io/deep%20learning/2016/05/20/Gradient-Descent-Algorithm-Overview.html

 

다음 그림을 보면, 빨간색인 SGD는 다른 개선안들 ( 다른 녀석들은 앞으로 다루게 될 개선안들입니다 )에 비해 굉장히 정체되어있음을 알 수 있습니다. 심지어 다른 local minima에 빠져 제대로 global optima에 수렴하지 못하는 상황도 발생하게 됩니다. 그러면 이러한 SGD를 다양한 방법을 통해 이 한계점을 극복하고자 하는 흐름들이 있었는데요. 그것을 다음과 같은 Flow로 정리해보았습니다.

 

출처 : 지식서비스를 위한 기계학습, 박찬영 교수님 강의자료

 

위 그림을 보면 크게 2가지 방향을 통해 개선 시도가 이루어졌습니다. 물론 이 2가지는 독립적이지 않고 Adam처럼 한꺼번에 쓰일 수 있습니다. 여기 중에서 본 포스팅에서는 'Momentum', 'Nesterov Momentum', 'AdaGrad', 'RMSProp' 그리고 'Adam' Optimizer에 대해 다루도록 하겠습니다. 

 

첫 번째로 우선 Momentum부터 살펴보겠습니다.

 

 

Momentum

'The method of momentum is designed to accelerate learning, especially in the face of high curvature, small but consistent gradients, or noisy gradients.' 

 

Ian GoodFellow et al. 은 책에서 momentum을 다음과 같이 이야기합니다. 즉, 쉽게 말해서 너무 느리다는 겁니다. 하지만 이 느린 것은 여러 문제를 낳게 되는데요, 대표적으로 local optima에 빠질 수 있는 문제를 낳습니다. 그림을 통해 설명드리겠습니다. 

 

다음 그림을 보면 f(x)에서 SGD를 수행할 때, 미분값이 0이 되는 부분에서 더 이상 optimize를 진행하지 않는 문제가 발생합니다. 굉장히 천천히 optimization이 이루어지는 경우 바로 이런 local optima에 더 쉽게 빠질 수 있게 됩니다. 

 

그래서 이 문제를 극복하기 위해 Momentum의 개념이 도입됩니다. 

Momentum(관성)은 변수가 가던 방향으로 계속 가도록 하는 속도(velocity) 항을 추가하는 방법을 통해 구현됩니다. 즉, 만약 GD가 바른 방향으로 가고 있다면 더 속도가 빨라지게 되어 더 빨리 훈련을 하게끔 해주어 현재 기울기가 0인 안정점이더라도 속도를 통해 더 이동함으로서 local optima에서 더 잘 탈출할 수 있게끔 하는 방법을 말합니다. 

 

그렇다면 구체적으로 그 속도는 어떻게 추가하는지 살펴보겠습니다. 

앞선 일반적인 SGD는 다음과 같이 가중치가 업데이트 됨을 확인할 수 있었습니다.

하지만 momentum이 적용된 수식은 조금 바뀌는데요 다음과 같이 변형됩니다.

위 수식에서 v는 velocity를 의미합니다. 즉, 일반적인 gradient를 바로 세타에 적용하는 것보다 velocity term을 추가해서 업데이트를 수행함을 확인할 수 있습니다. 예를 들어 위 미분의 결과가 0이라고 해보죠. 그러면 위 SGD에서는 g_hat이 0이 되기 때문에 더 이상 업데이트가 수행이 되지 않습니다. 하지만 아래 수식은 어떨까요? 아래 수식에서는 미분 값이 0이더라도 a*v term이 남아있기 때문에 여전히 업데이트가 진행됨을 확인할 수 있습니다. 위 수식에서 알파 값은 얼마나 빠르게 과거의 gradient의 영향도를 감소시킬 것인지를 적용하는 하이퍼 파라미터라고 보시면 좋을 것 같습니다. 

이 말은 무슨 의미일까요? 일반적으로 초반에는 이 알파 값을 매우 작은 값을 사용합니다. 왜냐면 초기 previous gradient 값이 신뢰할 수 있는 방향으로 update를 수행하는 지 알수 없기 때문이죠. 하지만 점차 process를 밟으면서 저 알파 값을 키우게 되어 점점 스텝 사이즈를 크게 만들게 됩니다. 즉 바른 방향으로 가고 있다면 더 속도를 빠르게 하는 것이죠. 

 

따라서 이와 같은 모멘텀을 적용한 SGD의 알고리즘은 다음과 같습니다. 

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

 

Nesterov Momentum

하지만 여기서 자연스럽게 떠오르는 질문이 있습니다. 저렇게 막 이동을 시켜버리면 정작 global optima에 도달했음에도 계속 진행을 시켜서 (이경영 아저씨 마냥) 멀리 가버리게 되면 문제가 생기지 않을까요? 

이런 경우에는 살짝의 휴리스틱을 적용해서 극복할 수 있는데요, 바로 다음과 같은 휴리스틱을 적용합니다. 

 

기존 Conventional momentum은 다음과 같이 update를 했다면

다음과 같이 업데이트를 하는 겁니다.

달라진 항목은 바로 Loss function 안에 있는 가중치 값인데요, 즉 바로 gradient를 xi에서 계산하는 것이 아닌, 관성에 의해 이동한 이후 gradient를 계산하는 것입니다. 이 방법을 Nesterov Momentum이라고 합니다.

 

그러면 이렇게 하면 정말 기존 momentum의 문제를 극복할 수 있을까요?

다음 그림을 살펴보겠습니다.

cs231n, Stanford Univ, Deep learning for Computer Vision

cs231 강의에서는 이것을 다음 그림을 통해 simple하게 설명하는데요, 우선 왼쪽에 있는 그림은 일반적인 momentum을 의미합니다. 이 경우, 기존 위치에서 velocity를 통해 실제 step을 정하게 되는데요 만약, velocity가 굉장히 큰 값이 들어오면 actual step은 그만큼 더 커지게 됩니다. 반면 nesterov의 경우 velocity가 커지게 되더라도 gradient가 그 정도를 보정하는 방향으로 움직임으로서 실제로 actual step이 커지게 되는 현상을 막게 됩니다. 

 

따라서 알고리즘은 다음과 같이 동작하게 됩니다.

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

 

AdaGrad

모멘텀을 통해 쉽게 이 문제가 해결되었다면 좋았겠지만, 아쉬운 부분은 모멘텀 알고리즘 또한 추가적인 하이퍼 파라미터 알파를 사용한다는 점이 한계점입니다. 왜냐하면 어떤 알파를 쓰냐에 따라 결국 성능에 큰 영향을 미치기 때문입니다. 따라서 직접적으로 learning rate를 적절하게 apply를 하자는 시도가 나오게 되었고 그 첫 시도로 수행된 방법이 바로 Adaptive Gradient ( AdaGrad ) 입니다. 

 

AdaGrad는 update할 때 각각의 변수마다 step size를 다르게 설정해서 업데이트를 수행하는 것을 기초로 합니다. 즉, 지금까지 많이 변화하지 않은 변수들은 step size를 크게 하고, 지금까지 많이 변화했던 변수들은 step size를 작게 하자는 아이디어에 기초합니다. 왜냐하면 변수가 자주 update 된다면 최적 값에 가까워졌다는 것을 의미하고, 이 때 이동거리를 짧게 주면 최적 값을 지나치지 않고 찾을 수 있게 됩니다. 하지만 반대로 업데이트가 자주되지 않는 변수의 경우, 이동 거리를 크게 해서 최적 값에 가깝게 만들어 시간을 단축하는 방법으로 동작을 수행합니다. 

 

다음 수식을 봐보죠

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

 

즉 처음에 gradient를 계산하는 것은 동일한데, 

두 번째 수식에서 r <- r + g*g 가 나옵니다.

즉, gradient를 제곱한 수식을 누적한 값이 등장하게 됩니다. 

 

변수 r의 경우는 상태가 변할 때마다 기울기의 제곱 값이 계속 더해지게 됩니다. 즉, 과거의 기울기를 바탕으로 시간이 지날수록 점점 더 커지게 됩니다. 이 커지는 r 값이 세 번째 수식인 분모에 들어가게 되면 점차 gradient에 들어가는 학습율을 낮추게 됩니다. 즉, history를 많이 가지고 있는 변수의 가중치는 업데이트가 덜 되는 거죠. 반면 그렇지 않은 변수의 가중치는 상대적으로 업데이트가 크게 될 겁니다. 

 

이러한 방법으로 동작하는 알고리즘은 다음과 같습니다.

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

 

하지만 여기서의 한계점은, 이 r의 값이 무한히 커지는 문제가 발생할 수 있게 됩니다. 이 경우 learning rate를 매우 작게 감소시키게 되어 이전 문제가 동일하게 발생하게 됩니다. 

RMSProp

그래서 이 문제를 극복하고자 등장한 개념이 바로 Root Mean Squared Prop (RMSProp) 입니다. 

이 RMSProp의 경우 AdaGrad처럼 모든 기울기를 단순히 전부 더하는 것이 아니라 최신 기울기 정보를 더 크게 반영해서 동작을 하는 방향으로 수정되었습니다. 즉 핵심인 learning rate가 너무 크게 감소하는 문제를 극복하고자 한 것입니다. 

 

즉 기존에는 다음과 같이 업데이트가 되었다면

 

 

 

다음과 같이 수정해서 적용된다는 점입니다.

 

 

즉 기존과 바뀐 부분은 바로 r 앞에 rho가 추가되고 gradient^2에도 (1-rho)가 추가되었다는 것을 알 수 있습니다.

 

이를 반영한 알고리즘은 다음과 같습니다.

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

Adam

GD가 수행되는 속도에 가속도를 붙여주는 모멘텀, learning rate를 조절해주는 RMSProp, 이 둘을 같이 사용하는 방법은 없을까라는 질문에서 시작된 것이 바로 Adam입니다. 말 그대로 Adam은 이 둘을 적절히 조합해서 활용을 하게 되는 optimizer 기법으로 현대에서 가장 많이 사용되고 있습니다. 논리는 단순합니다.

 

우선 전체 알고리즘은 다음과 같습니다.

출처 : Goodfellow, I., Bengio, Y., & Courville, A. (2016).  Deep learning . MIT press.

다음을 구체적으로 살펴보겠습니다.

 

여기서 위 'Update'가 들어간 두 문장을 살펴보면, 바로 첫 번째 부분은 velocity를 적용하기 위한 momentum term임을 알 수 있습니다. 즉 기존에는 s <- a*s - e*g 로 표기된 것이 a가 p1, e가 (1-p1)이 됨을 알 수 있습니다. 

또한 기존 RMSProp에서 사용한 accumulate gradient 값도 그대로 사용함을 알 수 있습니다. 

 

하지만 여기서 독특한 점이 correction bias 라고 하는 편향 보정을 수행해줍니다.  

알고리즘을 보면 처음에 s 와 r은 0으로 초기화합니다. 이런 경우 학습 절차에서 그대로 사용을 하게 되면 학습 초반에 s, r이 0이 되면 p1, p2가 1이 되게 되고, 이 모멘텀 계수가 기여가 전혀 없는 문제가 발생하게 됩니다. 따라서 이를 다음과 같이 s <- s/(1-p1), r <- r/(1-p2) 보정을 해줌으로써 0 근처로 쏠리는 문제를 보완하게 됩니다. 

 

 

Gradient-based Optimization을 잘 정리한 figure가 있어 추가적으로 공유합니다!

출처 : https://www.slideshare.net/yongho/ss-79607172

 

이렇게 이번 포스팅에서는 Momentum, Nesterov Momentum, AdaGrad, RMSProp, Adam에 대해 살펴보았습니다! 

긴 글 읽어주셔서 감사합니다!