Gradient Based Learning Algorithm (2)

이번글은 minibatch Stochastic Gradient Descent의 단점을 해결한 Momentum Algorithm들에 대하여 소개하도록 하겠습니다.

Deep Learning 책의 8장과, 'An overview of gradient descent optimization algorithms*'논문과 여러 기술 블로그들을 활용하여 작성하였고, 더 자세한 내용이 궁금하신 분들은 제가 참고한 자료들을 한번 보시는것을 추천드립니다.

momentum... 정말 논문과 교재들마다 표기가 다르고, 업데이트 해주는 값에 취해주는 부호도 달라서 이해하는데 꽤 애먹었네요.. 이론적 배경은 논문과 Deep Learning교재 모두 참고하고, 수식은 Deep Learning에 적힌 식을 기준으로 설명드리도록 하겠습니다.

먼저 momentum에 대하여 설명하기 앞서서, 논문에서 소개되는 minibatch Stochastic Gradient Descent 알고리즘이 해결해야할 문제 4가지를 짚고 가도록 하겠습니다.

========================================================================================================================

1. 적당한 값의 learning rate를 선택하는 것이 너무 어렵다.

- learning rate이 너무 크면,

* 수렴을 저해하고, minimum 주변을 왔다갔다 거리거나 발산해버립니다.

- learning rate이 너무 작으면,

* 너무 느리게 수렴하고, local minima에 빠지기 쉽습니다.

2. Learning rate의 schedule들과 threshold들은 미리 정의되어있어야 하고, 미리 정의되어야 하기 때문에 데이터셋들의 특성에 적응시킬 수 없다.

- learning rate schedule은 미리 정의된 schedule에 따라서 학습과정 도중 learning rate을 감소시키거나 담금질(annealing)하여 learning rate를 조정하거나, epoch 사이(현재 학습이 끝나고 다음학습의 시작 전 단계)에서 threshold 보다 떨어질 경우 learning rate을 바꾸는 것을 의미합니다.

** learning rate 담금질에 대해서는 설명이 너무 길어지는 관계로 'http://cs231n.github.io/neural-networks-3/#anneal' 를 참고하시기 바랍니다.

3. 모든 파라메터의 update에는 동일한 값의 learning rate이 적용된다.

- 데이터가 sparse하고(의미 있는 데이터가 적은 것을 의미합니다), feature들이 매우 다른 분포를 보일때, 드물게 보이는 중요한 feature들에 대해서만 큰 규모로 update를 수행하므로써 모든 파라메트들을 전부 같은 크기로 update하고 싶지 않지만 특정 상황에 따라서 특정 파라메터들만 update를 하는 것은 현실적으로 불가능합니다.

4. 수많은 suboptimal local minima(saddle point)에 갇히게 되는 것을 피해야 한다.

- 단순한 local minima를 빠져나오는 것보다 같은 error로 인해 만들어진 plateau(고원,안정적인 평평한 부분의 개념으로 이해하면 될것 같습니다)로 둘러싸인 saddle point를 빠져나오도록 하는 문제가 해결하기 더 어렵습니다. 특정지점을 둘러싸는 plateau는 모든 차원에서 gradient가 거의 0에 가깝기 때문에 SGD가 local minima를 빠져나오기 힘들게 만듭니다.

========================================================================================================================

minibatch SGD는 이 4가지 도전과제를 해결해야하는 문제를 안고 있기 때문에, 높은 곡률과 작지만 변동없는 gradient 혹은 noisy한 gradient의 상황에서 학습을 가속화시키도록 설계된 momentum을 적용한 SGD방식이 제안되었습니다.

1. SGD with Momentum

momentum은 파라메터 space에서 particle(입자)를 움직이는 힘(force)인 negative gradient를 뉴턴의 운동법칙에 따라서 물리학적으로 비유하면서 파생되었으며, momentum 알고리즘은 기하급수적으로 감소하는 이전 gradient들의 이동평균을 누적하고, 이동중이던 방향으로 계속 이동하도록 하는 알고리즘으로 Deep Learning 책에서 설명한 내용을 토대로 좀더 자세하게 살펴보겠습니다.

먼저, momentum 알고리즘의 이해를 위해 알아야 할 3가지 핵심요소가 있는데 다음과 같습니다.

* variable V(velocity;속도) : 파라메터가 파라메터 공간을 통해 이동하기 위한 방향과 속력을 의미하며, V는 기하급수적으로 감소하는 negative gradient의 평균으로 세팅됩니다.

* momentum : (물리학에서는 질량과 속도를 곱한 값) momentum learning 알고리즘에서는 unit mass로 가정하여, velocity vector V를 particle의 momentum으로 가정합니다.

* hyperparameter alpha(a) : 0이상 1미만의 값으로 이전 gradient들의 기여도가 얼마나 빠르게 기하급수적으로 감소될지를 결정합니다.

위 세가지 요건에 따라서 정의되는 momentum을 적용한 파라메터 update 규칙은 다음과 같습니다.

위 식에 따라서 V는 gradient element인 를 축적하는 것을 알 수 있고,

가 클수록 에 영향을 미쳐 현재 gradient에 이전 gradient의 영향이 커지게 됨을 알 수 있습니다.

뿐만 아니라, minibatch SGD까지는 step의 size가 단순히 gradient의 norm(벡터의 크기 개념으로 이해하시면 될 것 같습니다.)에 learning rate을 곱한것이었다면, momentum이 적용된 SGD에서는 gradient들의 sequence가 얼마나 일직선적으로 나열되어있고, 얼마나 큰지에 따라서 step의 size가 달라질 수 있게 됨을 알 수 있습니다. 따라서 step size는 많은 연속적인 gradient들이 같은 방향을 가리키고 있을때 최대값을 갖게 되겠죠.

momentum 기반의 SGD 알고리즘은 다음과 같습니다.

1. 먼저 Learning rate과 momentum parameter alpha의 초기값을 설정합니다.

* 실용적인 측면에서 alpha값은 0.5, 0.9, 0.99를 일반적으로 사용한다고 딥러닝 책에 기술되어있으니 참고하시기 바랍니다.

* 추가로 alpha값은 learning rate과 같이 학습의 진행에 따라서 adapted되어야 할 요소로써, 보통은 작은 값에서 시작하여 점점 증가시킨다고 합니다. 하지만 교재에서는 alpha값을 adapt시키는 것이 필요는 하지만, 학습의 진행에 따라서 learning rate을 감소시키는 것보다 덜 중요하다고 하네요.

2. weight와 bias 파라메터와 velocity V의 초기값을 설정합니다.

3. 학습데이터 셋으로 부터 m개의 데이터를 샘플링하여 minibatch 셋을 만듭니다.

4. 해당 minibatch 셋을 통해 평균 gradient값을 계산합니다.

5. velocity V를 설정한 값들을 기반으로 업데이트 합니다.

6. 업데이트 된 velocity V를 기반으로 weight, bias 파라메터를 업데이트 합니다.

7. 업데이트 된 파라메터들을 기반으로 validation error를 계산하여, 설정된 임계값보다 클때 다시 '3'으로 돌아가서 반복문을 수행하고, 임계값보다 작을 경우 while을 빠져나가 학습을 종료시킵니다.

다음은 momentum 기반의 SGD를 사용하는 경우와 그렇지 않은 경우 학습되는 과정을 논문에서 그림으로 표현한 것인데, 이해를 돕고자 첨부해보았습니다.

그림을 보면 a는 상당히 particle이 상당히 진동(oscillation)을 많이하며, 협곡 지점(ravine;타원의 가운데 부분)을 찾아가는데 어려움을 보이는 반면, b는 momentum이 적용되어, 수렴이 더 빨라지고 진동이 줄어드는 것을 확인할 수 있습니다.

이 그림은 Deep Learning책에 실린 momentum 알고리즘을 설명하는 사진인데, 위의 b가 왜 수렴이 더 빨라지고 진동이 줄어드는지에 대한 설명이 될 수 있는 그림인 것 같아서 첨부하였습니다.

두 번째 사진에서 검정색 선이 입자가 이동하려는 힘이고 빨간색 선이 실제로 입자가 이동한 경로인것을 인지하셨다면, momentum update는 particle이 이동하는 것을 마치 어떠한 힘이 작용하여, 학습을 최적화 시키는 것 처럼 보입니다.

momentum update는 최적화가 이루어지는 방향에 특정 힘을 가하여 minibatch SGD에서 발생하는 문제를 해결하도록 설계되었다고 위에서 언급하였는데요,

momentum update에서 학습의 속도(속력 + 방향)에는 두가지 힘이 가해집니다.

1. negative gradient of the cost function

: negative gradient of the cost function

첫 번째 힘은 손실함수로부터 계산된 gradient에 음의 값을 취한 값 입니다. 이힘은 cost function의 표면을 따라서 particle을 downhill로 밀어내는 작용을 합니다.

기본 GD 알고리즘은 각 단계의 gradient를 기반으로 한 스텝 나아가는데 gradient를 활용한다면, momentum 알고리즘은 negative gradient를 particle의 velocity로써 활용합니다.

아마 Deep Learning 책과 논문들이나 다양한 기술 블로그들마다 수식이 2가지로 정리가 되어있어서 저처럼 한동안 혼동하시는 분들이 있을 수도 있지 않을까 생각이 되는데, 해당식들은 이미 이 힘에 대한 전제가 깔려있기 때문에 저렇게 정리가 된 것입니다.

2. necessary

그런데, negative gradient of the cost function만이 particle에 가해지는 유일한 force라면, 학습은 쉬지않고 계속진행됩니다. Deep Learning 책에서는 이를 hockey puck(하키 경기에서 사용되는 공)에 비유을 했습니다. hockey puck이 얼음으로 이루어진 협곡형태의 지형을 내려갔다가 올라갔다가를 반복하고 있다고 가정을 한다면, 얼음으로 이루어진 협곡은 마찰이 거의 없다고 가정할 수 있기 때문에 계속 왔다갔다만을 반복하게 됩니다.(간단한 물리개념이 좀 필요할 것 같네요.)

이 문제를 해결하기 위해서 추가된 또하나의 힘이 바로 - v(t)입니다. Deep Learning 책에서 이 힘을 점성(viscous)을 가지고 drag하는 시럽(설탕물 끓인것)으로 표현을 하네요. 이 힘을 통해서 시간이 갈수록 입자가 점점 힘을 잃게 함으로써 local minimum으로 수렴되도록 하는 것입니다.

만약, 건조마찰과 같은 0에 가까운 힘이 가해진다면, 기존에 존재하는 force는 상대적으로 너무 강하게 되는 문제가 발생하고, 또 손실함수의 gradient로 인한 힘이 0은 아니지만 작을 경우, 마찰로 인한 지속적으로 가해지는 힘을 통해 minimum에 도달하기 전에 멈춰버리게 만듭니다. 따라서 viscous drag방식인 두번째 힘은 gradient가 minimum에 도달할때까지 움직임을 지속하게 할수 있도록 작으면서도, gradient의 움직임이 정당한방향(협곡지점으로 수렴하는 방향)으로 이동하지 않을 경우, 움직임을 저지할 수 있을 정도로 큰 힘이라는 것에서 Deep Learning 책에서 necessary라고 표현을 합니다.

2. SGD with Nesterov Momentum

Nesterov momentum 방식은 Standard Momentum 업데이트 알고리즘 방식에서 gradient가 evaluate되는 것입니다. 즉, 현재 시점의 velocity를 적용하고나서 gradient를 평가하는 것이 Nesterov momentum(Nesterov accelerated gradient; NAG)방식입니다. 평가한다는 개념이 마치 앞으로의 학습이 이루어지는 속도(방향 + 속력)을 예측하는 것과 비슷하다고 이해하시면 될 것 같습니다.

Nesterov 방식은 기존의 Standard 방식에서 particle이 맹목적으로 경사면을 따라서 언덕을 내려가는 것이 매우 불만족스러운 결과를 초래할 가능성이 높아 기존의 Standard를 개선하여 만들어진 방식입니다.

업데이트 식은 다음과 같이 정리됩니다.